正整數分解為幾個連續自然數之和

題目：輸入一個正整數，若該數能用幾個連續正整數之和表示，則輸出所有可能的正整數序列。

一個正整數有可能可以被表示為n(n>=2)個連續正整數之和，如：

15=1+2+3+4+5

15=4+5+6

15=7+8

有些數可以寫成連續n（>1）個自然數之和，比如14=2+3+4+5；有些不能，比如8.那麼如何判斷一個數是否可以寫成連續n個自然數之和呢？

一個數m若可以寫成以a開頭的連續n個自然數之和，則m=a+(a+1)+(a+2)+…+(a+n-1)=n*a+n*(n-1)/2，要求a!=0，否則就是以a+1開頭的連續n-1個整數了，也就是要求(m-n*(n-1)/2)%n==0，這樣就很容易判斷一個數可不可以寫成連續n個自然數的形式了，周遊n=2…sqrt(m)*2，還可以輸出所有解。

第二個問題是什麼樣的數可以寫成連續n個自然數之和，什麼樣的數不能？

通過程式設計實驗發現，除了2^n以外，其餘所有數都可以寫成該形式。下面說明為什麼。

若數m符合條件，則有m=a+(a+1)+(a+2)+…+(a+n-1)=(2*a+n-1)*n/2，而2*a+n-1與n肯定一個為奇數一個為偶數，即m一定要有一個奇數因子，而所有2^n都沒有奇數因子，是以肯定不符合條件。

再證明隻有m有一個奇數因子，即m!=2^n，m就可以寫成連續n個自然數之和。假設m有一個奇數因子a，則m=a*b。

若b也是奇數，隻要b-(a-1)/2>0，m就可以寫成以b-(a-1)/2開頭的連續a個自然數；将這條結論裡的a和b調換，仍然成立。15=3*5=1+2+3+4+5=4+5+6.

若b是偶數，則我們有一個奇數a和一個偶數b。

2.1 若b-(a-1)/2>0，m就可以寫成以b-(a-1)/2開頭的連續a個自然數。24=3*8=7+8+9.

2.2 若(a+1)/2-b>0，m就可以寫成以(a+1)/2-b開頭的連續2*b個自然數。38=19*2=8+9+10+11.

上述兩個不等式必然至少有一個成立，是以可以證明，隻要m有一個奇數因子，就一定可以寫成連續n個自然數之和。

另一個正整數分解的算法：

sum(i,j)為i累加到j的和 

令 i=1 j=2 

if sum(i,j)>n i++ 

else if sum(i,j)<n j++ 

else cout i...j 

參考代碼：

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。