hdu 2058 The sum problem(数学题)-程序员宅基地

技术标签: 等差数列  数论  hdu  acm  数学题  

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2058

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18137    Accepted Submission(s): 5385


Problem Description
Given a sequence 1,2,3,......N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.
 
Input
Input contains multiple test cases. each case contains two integers N, M( 1 <= N, M <= 1000000000).input ends with N = M = 0.
 
Output
For each test case, print all the possible sub-sequence that its sum is M.The format is show in the sample below.print a blank line after each test case.
 
Sample Input
  
  
   
20 10 50 30 0 0
 
Sample Output
  
  
   
[1,4] [10,10] [4,8] [6,9] [9,11] [30,30]


【分析】

每组输入两个数n,m

问从1~n 个数中有多少连续区间的和等于m,如果等于,输出该区间

容易想到等差数列的公式 Sn=(a1+an)*n /2

也许高中时讲过上面公式的变形  Sn=a1*n+(n-1)*n*d/2; (Sn=(a1+a1+(n-1)*d)*n/2 = a1*n+(n-1)*n/2)

又因为本题d=1; Sn=a1*n+(n-1)*n/2;

对于任意这样的等差数列,什么时候n最大呢?

显然当a1=1的时候 n最大, 所以,化简一下,此时的Sn*2 = n*(n-1);

也就是说 n小于 sqrt(Sn*2);

所以我们只要把n从最大到1进行遍历求解就行了,(时间上大大的优化了)

因 a1*n + n(n-1)/2 =  Sn;

所以我们设 b = Sn - n*(n-1)/2;

那么只要 b % n == 0 那么就找到了所求区间 【b/n+1,b/n+n】,该区间元素和等于Sn;

【代码如下】

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		if(n==0&&m==0)
			break;
		for(int i=sqrt(m*2);i>0;i--)
		{
			int b=(m-(i*i+i)/2);
			if(b%i==0)
			{
				printf("[%d,%d]\n",b/i+1,b/i+i);
			}
		}
		printf("\n");
	}
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/chaiwenjun000/article/details/46291405

智能推荐

UIL神器-程序员宅基地

文章浏览阅读50次。Android开源代码精选之ImageLoaderAndroid开发中最常用到的组件,非ImageLoader莫属。源码地址:https://github.com/nostra13/Android-Universal-Image-Loader[上代码]:1. 添加jar包2. 修改Android Manifest,添加网络请求和写文件权限?代码片段[email protected]

动态内存管理_C_不申请内存,堆空间在减少-程序员宅基地

文章浏览阅读324次。一、函数介绍 以下四个函数都包含在头文件&lt; stdlib.h &gt;1.malloc 函数原型:void *malloc(size_t size); 作用:从堆空间申请内存 函数参数:需要申请的空间大小(字节数) 返回值:申请成功则返回一个指向申请到的内存的指针,失败则返回NULL2.calloc 函数原型:void *calloc(size_t num,siz..._不申请内存,堆空间在减少

ORACLE之rman备份:ORA-19809和ORA-19804的解决方法_cannot reclaim 67108864 bytes disk space from 1073-程序员宅基地

文章浏览阅读1.8k次。操作环境:redhat 6.4 oracle 12crman备份出错。之前出现过,好象重新backup database就可以了,今天又出现,纪录下RMAN-03009: failure of Contrl file and SPFILE Autobackup command on ORA_DISK_1 channel at 06/06/2018 13:43:50ORA-19809: limit..._cannot reclaim 67108864 bytes disk space from 10737418240 bytes limit

2022年雷达领域学术会议时间节点_iet radar conference 2023-程序员宅基地

文章浏览阅读5k次,点赞5次,收藏9次。IET Radar 2022radar2022October 2022 | Scotland, UKFull paper submission deadline 18 April 2022Author notification 27 June 2022Final revised paper deadline 4 July 2022Author registration deadline 18 July 2022Theme C - Remote Sensing from Airborne_iet radar conference 2023

Clion变量无法跳转到声明处_clion 找不到要转到的声明-程序员宅基地

文章浏览阅读8.1k次。问题:使用Clion查看代码时,对某变量ctrl+鼠标左键能跳转到该变量声明处,但有时会失败。解决方法:重启Clion,再次打开该工程,会自动重新加载符号,然后就能跳转成功。..._clion 找不到要转到的声明

分享一个It学习的好网站itsoku-程序员宅基地

文章浏览阅读264次。最近去学习一个新东西的时候,无意间发现一个比较不错的学习网站推荐给大家,www.itsoku.com 里面的学习教程和博文都不错。_itsoku

随便推点

kubeflow二次开发--独立module开发_kubeflow前端二次开发-程序员宅基地

文章浏览阅读692次。一、介绍二、开始coding1、Dockerfile内容2、yaml文件3、build docker image4、创建pod和service5、访问一、介绍系统:Centos7Kubeflow版本:0.7.0Pipeline版本:0.1.31Go版本:1.13前后端不分离的一个应用,目录结构如下public存放静态资源src是api代码主要功能是查询数据库数据,然后在网页显示用到了gin框架,起http服务Gorm作为orm框架代码已上传我的githubhttps://gith._kubeflow前端二次开发

floor() 函数_floor()函数-程序员宅基地

文章浏览阅读4.9k次,点赞6次,收藏13次。查看更多https://www.yuque.com/docs/share/2a8366d1-bdc5-4faf-95ed-655beea8d8f9_floor()函数

74cms CSRF漏洞可以诱骗添加管理员-程序员宅基地

文章浏览阅读2.3k次。74cms CSRF漏洞可以诱骗添加管理员

少年郎,我这里有一份nginx配置,你拿走吧-程序员宅基地

文章浏览阅读5.7k次。首先,直接上干货:user root;worker_processes 4;error_log /var/log/nginx/error.log;#pid logs/nginx.pid;events { use epoll; worker_connections 65536; accept_mutex on; multi_acc..._large_client_header_buffers 4 128k; underscores_in_headers on; client_header

「小程序」信息无障碍初体验_微信小程序无障碍版本-程序员宅基地

文章浏览阅读1k次。是的,千呼万唤,微信小程序始出来。微信小程序正式发布后,中国信息无障碍产品联盟(CAPA)的信息无障碍工程师们在第一时间对其无障碍情况进行了体验。共选取了滴滴出行DiDi、饿了么外卖服务、今日头条lite三款小程序,在Android及iOS平台上分别通过读屏软件进行操作使用,并记录下其对应的表现。 体验所使用的机型及相关环境如下: 华为 P9 + Android 7.0 + EMui 5..._微信小程序无障碍版本

FPGA的基本组成结构_fpga组成-程序员宅基地

文章浏览阅读1.8w次,点赞11次,收藏146次。目前主流的FPGA芯片仍是基于查找表。FPGA芯片主要由以下6部分组成:(1)可编程输入输出单元(IOB)(2)基本可编程逻辑单元(CLB)(3)完整的时钟管理模块(4)丰富的布线资源(5)嵌入式块RAM(6)内嵌的底层功能单元和嵌入式专用硬核通过配置以上6个不同的部分,基本可以让FPGA实现任何你想要实现的功能。一、FPGA的结构解析对于一款芯片,我们肉眼看到..._fpga组成