连续正整数

还是数据结构的网上作业，将一个整数分解为连续正整数之和，找对方向倒是也不算难……

有些正整数可以表示为 n (n>1) 个连续正整数的和，如：

15=1+2+3+4+5
    =4+5+6
    =7+8

给定一个正整数 N，判断其是否可以表示为一组连续正整数的和，输出符合条件的解的组数。

Input

输入有一行，包含一个正整数 n (3≤n≤1000000000)。

Output

输出有一行，正整数n的符合条件的解的组数。

Example

Input	Output
15	3
99	5
6	1
9	2

单点时限: 2.0 sec 内存限制: 256 MB

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int counter=0;
    for(int i=2; i<(100000<n?100000:n); i++) //n/i-i/2+1>=1
    {
        if(n/i-i/2-i%2+1>=1&&(n/i-i/2-i%2+1+n/i-i/2-i%2+1+i-1)*i==n*2)
        {
            counter++;
        }
        //cout<<"test-"<<i<<endl;
    }
    cout << counter << endl;
    return 0;
}

枚举就好了。需要根据分成的整数的个数i讨论，但为了显得更牛X我就写到一起了，上面的n/i-i/2-i%2+1无论在奇偶情况下都是拆分得到的整数的第一个理应是多少。

判断的主要逻辑：

第一个数字大于等于1
所有数之和等于原数

求和在这里就不必用循环了，用等差数列明显更高效。注意这里计算时为了防止整数除法运算截断的问题，将除法移动到了等式的右边。

最后修改于 2019-04-06