判断一个正整数是否可以由连续正整数求和而来

58同城面试遇到的问题，判断一个正整数n是否可以由连续正整数求和而来。我没回答上来，面试官给了提示，回来自己想想，觉得有两种方法：

1. 模拟法：用一个在数轴上的滑动窗（即一个正整数区间），来模拟求解过程。具体来说，如果滑动窗内整数的和小于n，则滑动窗右边界向右移动，如果滑动窗内整数的和大于n，则滑动窗左边界向右移动，如果滑动窗内整数的和等于n，则n可以由滑动窗内的整数求和表示，程序终止。
2. 数学分析法：可以证明（证明在本文最后），如果n可以表示为：n=(2*m+1)*2^k, m, k>=0; 则m>0时，n可以由连续正整数求和而来，m=0时，n不可以由连续正整数求和而来。实际上，正整数中，只有2的各次方不可以由连续正整数求和而来，如n=1,2,4,8,16,32... ;另一方面，只要n含有大于1的奇数因子，都可以由连续正整数求和而来。

下面是代码：

#include <iostream>
using namespace std;

//模拟法
bool valid(int n){
    if(n<=1) return false;
    //定义滑动窗的参数，first: 滑动窗左边界，last: 滑动窗右边界，sum: 滑动窗内整数的和
    int first, last, sum;
    //参数初始化
    first=last=sum=1;
    do{
        //n>sum, 则滑动窗右边界向右移动
        if(n>sum)    {
            last++;
            sum+=last;
        }
        //n<sum, 则滑动窗左边界向右移动
        else if(n<sum) {
            sum-=first;
            first++;
        }
        //n==sum, 循环结束，返回true
        else
            return true;
    }
    while(first!=last); //如果滑动窗只含一个整数，循环结束，返回false
    return false;
}

//数学分析法
bool valid2(int n){
    while(n%2==0) n/=2;
    return n>1;
}

int main()
{
    for(int i=1;i<=1000;i++)
        if(!valid(i))
            cout<<i<<endl;
    for(int i=1;i<=1000;i++)
        if(!valid2(i))
            cout<<i<<endl;
    return 0;
}

程序的运行结果就不贴出来了，有兴趣的话，可以自己试试。下面来证明前面提到的一个结论：如果n可以表示为：n=(2*m+1)*2^k, m, k>=0; 则m>0时，n可以由连续正整数求和而来，m=0时，n不可以由连续正整数求和而来。
证明：假设n可以由正整数区间[k₁,k₂],k₂>k₁>0内的整数求和而来，即

• n=(k₁+k₂)(k₂-k₁+1)/2=(2*m+1)*2^k, m, k>=0, k₂>=k₁>0; 即
• (k₁+k₂)(k₂-k₁+1)=(2*m+1)*2^k+1

容易证明，(k₁+k₂)和(k₂-k₁+1)奇偶性不一致，即一奇一偶。如果(k₁+k₂)为奇数，可以有(m=0时，只有)

• k₁+k₂=2*m+1;
• k₂-k₁+1=2^k+1;

求得k₁=m+1-2^k;k₂=m+2^k;同理如果(k₂-k₁+1)为奇数，可以有（m=0时，只有）

• k₂-k₁+1=2*m+1;
• k₁+k₂=2^k+1;

求得k₁=2^k-m;k₂=m+2^k;
看上去可以得到两个区间[2^k-m, m+2^k]和[m+1-2^k, m+2^k]（实际上m>0时，最后得到的区间可能更多），但是就这两个区间区间而言，不会同时有效。
来看看最后的结论，m=0时，两个区间都无效，说明此时，n不可以由正整数区间[k₁,k₂],k₂>k₁>0内的整数求和而来。
0<m<2^k 时，[2^k-m, m+2^k]有效；m>=2^k 时，[m+1-2^k, m+2^k]有效。即m>0, n至少可以由一个正整数区间[k₁,k₂],k₂>k₁>0内的整数求和而来。
证明结束！

---

最后，不足之处，不吝赐教！