The Sum Problem HDU 2058

[My blog https://dyingdown.github.io/

The Sum Problem

Problem

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]
           

Analysis

n a 1 + n ( n + 1 ) 2 = m 2 n a 1 + n ( n − 1 ) = 2 m a 1 = n m − n − 1 2 na_1+ \frac{n(n+1)}{2} = m \\2na_1 + n(n - 1) = 2m \\a_1 = \frac{n}{m} - \frac{n-1}{2} na1​+2n(n+1)​=m2na1​+n(n−1)=2ma1​=mn​−2n−1​

Code

#include<bits/stdc++.h>

using namespace std;

int main(){
	int n, m;
	while(cin >> n >> m && m != 0 && n != 0){
		for(int i = sqrt(2 * m); i > 0 ; i --){
			if(2*m % i == 0){
				if((2*m/i - (i-1)) % 2 == 0){
					cout << "[" << (2*m/i - (i-1)) / 2 << ',' << (2*m/i - (i-1)) / 2 + i - 1 <<']' << endl;
				}
			}
		}
		cout << endl;
	}
	return 0;
}