百度之星的一道题的解法

前段时间在CSDN上溜达的时候发现有人发帖问一道算法题的解法，看到之后感觉很有意思。题目如下

题目描述：一个正整数有可能可以被表示为 n(n>=2) 个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。

看到这道题后很容易想到第一中解法，就是2层循环的解法。不过感觉该算法的效率太低，我看到这个题目就立即想起了求和公式，我知道肯定有效率高的解法，刚好也没事就想着做做看。经过了一段时间的推导，我终于把程序完成了。程序代码如下，使用C++写得。

 int main(void) {

     int n; 

    cout<<"please input a num: n="; 

   cin>>n; 

  if(n%2) 

       cout<<n/2<<" "<<n/2+1<<endl; 

  for(int i=3;i<n;++i){ 

      if(!(2*n%i)&&(i*i+i>2*n)){

          int temp=i-(i+2*n/i-1)/2;   

          for(int j=0;j<2*n/i;++j)     

                 cout<<temp+j<<" ";   

         cout<<endl; 

     }

  }

}

程序大概就是这个样子，感觉这样写出来的程序效率就比常规的解法要高很多，达到了O（n）级别。整个程序的主要思路就是围绕着求和公式进行的，只要稍微推导下就能明白程序的意思了。

若一个数k满足题目的要求，比如可以分解成k=m+(m+1)+....+n，那么按照求和公式可以得到等式：

(m+n)*(n-m+1)/2=k   ------>  2*k=(m+n)*(n-m+1);   ----->   2*k一定可以分解成2个整数相乘，即可以被2个整数整除。设m+n=i    ------>    n-m+1=2*k/i    ------>  m=i-i+(2*k/i-1)/2   根据题目要求 m>0 就可以得出约束条件，这样再看程序就一目了然。

       后来我又从百度之星上发现了这道题，才知道原来是2005的第一题。