题目描述
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
暴力枚举,会超时
C++代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
int n, m;
while(cin >> n >> m && n != 0 && m != 0)
{
int t = 0;
for(int i = 1; i <= n; i ++)
{
for(int j = i; j <= n; j ++)
{
t += j;
if(t == m)
{
cout << '[' << i << ',' << j << ']' << endl;
}
}
t = 0;
}
puts("");
}
return 0;
}
算法2
数学规律,不会超时
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
int n, m, i, j, len;
while(cin >> n >> m && n != 0 && m != 0)
{
for(len = sqrt(2 * m); len >= 1; len --)
{
i = (2 * m / len + 1 - len) / 2;
j = i + len - 1;
if((i + j) * len / 2 == m) cout << '[' << i << ',' << j << ']' << endl;
}
cout << endl;
}
return 0;
}