HDU 2058 The sum problem

The sum problem
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12104 Accepted Submission(s): 3666

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]
總結:

觀察a+1,a+2…a+d
全部相加等於M
即(a+1+a+d)*d/2 = M,
這裡d是平方，我們可以從長度d入手，這樣就能把范圍由M轉換成M^1/2 ;

這裡把代碼中的①和②解釋下：
①：當a+1,a+2…a+3相加等於M時，即
(a+1+a+d)*d/2 = M
而a最小是0，所以(d+1)*d/2=M時d去最大值，就是這步把時間復雜度減小的。
d就是sqrt(2*M)

②：(a+1+a+d)*d/2 = M
所以a*d + (d+1)/2 = M
所以要使等式成立，M-(d+1)/2必須是d的倍數。

import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(new BufferedInputStream(System.in));
		while(sc.hasNextInt()){ 
			int n=sc.nextInt();
			int m=sc.nextInt();
			if(n==0&&m==0)
				System.exit(0);
			int t1=(int)Math.sqrt(2*m);
			for(int i=t1;i>=1;i--){
				long temp=m-(i*i+i)/2;
				if(temp%i==0)
					System.out.println("["+(temp/i+1)+","+(temp/i+i)+"]");
			}
			System.out.println();
		}
		
	}
	
}