The sum problem
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20726 Accepted Submission(s): 6100
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]
Author
8600
Source
Recommend
linle | We have carefully selected several similar problems for you: 20592062206020722061
Statistic | Submit | Discuss | Note
这道题显然不可能直接暴力做出来。技巧在于所有可能数列的长度有最大值。设数列为a+1，a+2 ，…… a+len，则它的长度为len。
根据公式M=[(a+1)+(a+len)]*len/2化简得出M*2=len*len+(2a+1)*len。所以len一定小于sqrt（2*M）接下来就可以枚举lenAC这道题。
#include<stdio.h>
#include<math.h> int main()
{
int N, M;
while(~scanf("%d%d", &N, &M)) {
if(M == && N == ) break;
int len = sqrt(double(M * ));//如果不加double会出现编译错误，sqrt的参数是浮点型的。
while(len) {
int a = M / len - ( + len) / ;
if((a + + a + len) * len / == M) printf("[%d,%d]\n", a + , a + len);
len--;
}
puts("");
}
return ;
}