欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

The Sum Problem HDU 2058

程序员文章站 2022-05-17 20:58:54
...

[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

na1+n(n+1)2=m2na1+n(n1)=2ma1=nmn12 na_1+ \frac{n(n+1)}{2} = m \\2na_1 + n(n - 1) = 2m \\a_1 = \frac{n}{m} - \frac{n-1}{2}

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;
}
相关标签: Problem