《編》書(shū)2.21題信轿。
4 + 5 = 9
2 + 3 + 4 = 9
有些數(shù)比如 4 和 8 不能分拆寫(xiě)成連續(xù)自然數(shù)的和阔加。這裡面有什麼規(guī)律呢姑荷？如果用程序的思路來(lái)寫(xiě)街望，顯然可以使用蠻力窮舉可以求解。
這裡面有兩個(gè)信息：“連續(xù)” 和 “求和”踱稍。
我們先看最簡(jiǎn)單情況曲饱，兩個(gè)連續(xù)自然數(shù)相加悠抹。其和必為奇數(shù)，故偶數(shù)必不可以寫(xiě)成兩個(gè)連續(xù)自然數(shù)相加扩淀。而所有的奇數(shù)（2n+1）都可以寫(xiě)成兩個(gè)連續(xù)自然數(shù)相加楔敌，有且只有n, n+1這兩個(gè)數(shù)才滿(mǎn)足。
我們由此想到引矩，要將一個(gè)數(shù)寫(xiě)成m個(gè)連續(xù)自然數(shù)之和梁丘，這些數(shù)只能聚集在floor(1/m)處侵浸，並在該處左右各取數(shù)字旺韭，來(lái)彌補(bǔ)偏差。
而一個(gè)數(shù) x 最多可以寫(xiě)成多少個(gè)連續(xù)自然數(shù)之和呢区端？只能從1開(kāi)始取。我們有了1+...+m = x這個(gè)熟悉的式子澳腹。所以知道m(xù)最多是floor((sqrt(8x+1)-1)/2)织盼。
而且我們還知道，如果一個(gè)數(shù)能寫(xiě)成奇數(shù)個(gè)（假設(shè)為m）連續(xù)自然數(shù)相加的話(huà)酱塔，那該數(shù)必被m整除沥邻，即..., n-2, n-1, n, n+1, n+2, ...之和為 m*n，易知x % m = 0羊娃。
那偶數(shù)（m>2）的情況呢唐全？
同理，n, n+1, n+2, ... 之和為m*n+ m*(m-1)/2蕊玷，則x % m = m/2邮利。推導(dǎo)如下：
? ? x % m
= (m*n + m2/2 - m/2) % m
= (m2/2) % m - (m/2) % m
= (m * (m/2)) % m - (m/2) % m
= m/2 % m
= m/2
至此，我們可以用o(1)的方法驗(yàn)證一個(gè)自然數(shù)是否可以寫(xiě)成任意m個(gè)連續(xù)自然數(shù)的和了垃帅。
