hdu 2058_HAL248

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用
The sum problem

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 24299 Accepted Submission(s): 7247

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]

刚看到这道题，开始想将1开头的子序列找完，然后是2，依次向下找，这里我们可以选择一直找到n，但是会超时，如果选择找到某个最大的介于1到n之间的数，那么我们首先要计算那个介于1到n之间的最大的数，发现无法计算。我们可以选择另一条思路，先算出子序列的最大长度，既然是从1到n的序列，我们可以根据等差数列计算，既然是最大长度，那么一定是从1开始（数字选择的越小，使用的数字越多，长度就越长），根据长度来计算子序列，如图所示

代码如下

#include<stdio.h>

#include<math.h>

int main() {

long long n,m,i,j,s = 0;

scanf(“%lld%lld”,&n,&m);

while(n != 0 && m != 0) {

if(n == 0 || m == 0)

return 0;

for(i = sqrt(2 * m); i > 0; i–) {

s = m / i – (i – 1) / 2;

if(s + i – 1 <= n && (s + s + i-1) * i == 2 * m) //防止（s+s+i-1）*i不等于2m，可能由于s的值在计算时，是约等的。

//对于s + i -1 <=n 一定要判断，因为如果输入的n值很小，

//但是m值很大，（2m）的开平方，可能大于n，如n=5，m=30

printf(“[%lld,%lld]\n”,s,s + i – 1);

}

printf(“\n”);

scanf(“%lld%lld”,&n,&m);

}

return 0;

}