判断整数能否写成连续整数之和

问题：

Problem

Most positive integers may be written as a sum of a sequence of at least two consecutive positive integers. For instance,

6 = 1 + 2 + 3
9 = 5 + 4 = 2 + 3 + 4

but 8 cannot be so written.

Write a program which will compute how many different ways an input number may be written as a sum of a sequence of at least two consecutive positive integers.

Input

The first line of input will contain the number of problem instances N on a line by itself, (1<=N<=1000) . This will be followed by N lines, one for each problem instance. Each problem line will have the problem number, a single space and the number to be written as a sequence of consecutive positive integers. The second number will be less than 2^31 (so will fit in a 32-bit integer).

Output

The output for each problem instance will be a single line containing the problem number, a single space and the number of ways the input number can be written as a sequence of consecutive positive integers.

	Sample Input Copy to clipboard 7 1 6 2 9 3 8 4 1800 5 987654321 6 987654323 7 987654325

Sample Output

1 1 
2 2 
3 0 
4 8 
5 17 
6 1 
7 23

一开始的想法比较弱智，设n可以用s个连续整数表示，并且第一个数字是a。所以有s*a+s(s-1)/2 = n
并且a大于等于小于等于n/2。对a用循环，求出一元二次方程s的解，再判断是否为整数。超级烂，超级浪费
时间。

   #include

03. 

04.#include

05. 

06.using namespace std;

07. 

08.int main()

09.{

10.    int time, number, n, x, count;

11.    cin>>time;

12.    for(int i = 0; i < time; i++)

13.    {

14.        count = 0;

15.        cin>>number>>n;

16.        for(int j = 0; j < n/2; j++)

17.        {

18.            x = int((sqrt((2*double(j) + 1)*(2*double(j) + 1) + 8*double(n)) -  2*j -1)/2);

19.            if(x*x + (2*j + 1)*x - 2*n == 0)

20.                count++;

21.        }

22.        cout<" "<

23.    }

24.    return 0;

25.}


优化算法：
还是从s开始考虑，分别列出几项符合要求的整数来找规律。
s=2   3 5 7 9 11 13 .....
s=3   6 9 12 15 18 21 .....
s=4   10 14 18 22 .....
......
对于第一行，3=1+2,后面是公差为2的等差数列
对于第二行，6=1+2+3,后面是公差为3的等差数列
一次类推。。。。
下面求出对于不同n，s的范围
s(s+1)/2 <= n,一元二次方程可以解出s的范围
下面只要判断n是否属于s的哪一行中。。。

由于都是等差数列，所以判断 (n - s(s+1)/2)%s == 0
代码如下：




02.#include

03. 

04.#include

05. 

06.using namespace std;

07. 

08.int main()

09.{

10.    int time, count, number, n, s;

11.    cin>>time;

12.    for(int i = 0; i < time; i++)

13.    {

14.        count = 0;

15.        cin>>number>>n;

16.        for(s =2; s < int (sqrt(8*double(n) + 1)/2) + 1; s++)

17.            if((n - s*(s - 1)/2) % s == 0)

18.                count++;

19.        cout<" "<

20.    }

21.    return 0;

22.}