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
Sample Output
[1,4] [10,10] [4,8] [6,9] [9,11] [30,30]
思路：
1.由高斯求和公式文字表述：和=(首项 + 末项）x项数 /2可知：
区间[a,b]的各项和且b=a+i-1
2.转化该式子求出a，由a即可推导出b
(a+b)*i/2 = m(a+b)*i = 2*m(a+ a+i-1)*i = 2*m2*a = 2*m/i + 1 – ia = m/i –(i-1)/2
3.限定循环次数，条件需满足a>=1，即m/i –(i-1)/2>=1，化简可得i <= (int)Math.sqrt(2 * m)
AC代码：
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
//暴力法，但会LTE
// if (m == 0 && n == 0) {
// break;
// }
// for (int i = 1; i <= m; i++) {
// int sum = 0;
// for (int j = i; j <= m; j++) {
// sum += j;
// if (sum == m) {
// System.out.println("[" + i + "," + j + "]");
// }
// }
// }
// System.out.println();
//高斯公式法
if(n == 0 && m == 0){
break;
}
int a,b;
for(int i = (int)Math.sqrt(2 * m); i > 0; i--){
a = m / i - (i - 1) / 2;
b = a + i - 1;
if((a + b) * i == 2 * m){
System.out.println("[" + a + "," + b +"]");
}
}
System.out.println();
}
}
}