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

时间：2010-05-01 来源：zbhknightMJ

问题：
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<iostream>

03. 04.#include<cmath> 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<<number<<" "<<count<<endl; 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<iostream> 03. 04.#include<cmath> 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<<number<<" "<<count<<endl; 20.    } 21.    return 0; 22.}