The sum problem
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 21416 Accepted Submission(s): 6287
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、此题是公差为1的等差数列；
3、此题的n,m很大（不可能模拟所有的起点和终点）；
技巧转换：
只模拟起点和数列的长度，知道起点i和数列长度j，很容易根据等差数列公式求得这个子序列的和：(i+(i+j-1))*j/2;
化简公式得：
j*j+(2*i-1)=2*m;因为i>=1,m已知，所以j的取值为：j<=sqrt(2*m);
所以知道这个规律就可以写这个题了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<map>
#include<math.h>
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
#define IN __int64
#define N 10010
#define M 1000000007
using namespace std;
int main()
{
int n,m,i,j;
while(scanf("%d%d",&n,&m),n|m)
{
for(j=sqrt(2*m);j>0;j--)
{
i=(2*m/j-j+1)/2;
if(j*(j+2*i-1)/2==m)
printf("[%d,%d]\n",i,i+j-1);
}
printf("\n");
}
return 0;
}标签：case,2058,sum,long,each,problem,include,define From： https://blog.51cto.com/u_16079508/6206444