The sum problem
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
50 30
0 0
Sample Output
[1,4]
[10,10]
[10,10]
[4,8]
[6,9]
[9,11]
[30,30]
Sample Input
本来想前缀和搞搞的，一看1 <= N, M <= 1000000000，看来是公式题，给出一个M，不可能从1枚举到1000000000，所以要找一个枚举范围，等差数列求和公式：sum=n*a1+n*(n-1)/2,n要最大,就要a1=1,所以sum=n*(n+1)/2,变一下n<sqrt(2*sum),所以取n=sqrt(2*sum),接下来n从大到小枚举,用公式变形:a1=sum/n-(n-1)/2求出a1,求和如果等于M,输出[a1,a1+n-1].
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#define PI acos(-1.0)
#define ms(a) memset(a,0,sizeof(a))
#define msp memset(mp,0,sizeof(mp))
#define msv memset(vis,0,sizeof(vis))
using namespace std;
//#define LOCAL
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
//freopen("out.txt","w",stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
int n,m;
while(cin>>n>>m,n||m)
{
int t=sqrt(*m);
while(t)
{
int ans=m/t-(t-)/;
if(ans*t+(t*(t-)/)==m)
printf("[%d,%d]\n",ans,ans+t-);
t--;
}
printf("\n");
}
return ;
}