[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;
}