S=a + (a + 1) + (a + 2) + ...... + b（其中a, b > 0）
现在我们要求，给定一个正整数S，求有多少种不同的<a,b>，使得上述的等式成立。
这个问题很有意思，我猜大家一定想出了比较简单的那个方法了。
方法1：
代码大概是这个样子的：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int
sum = 0;
for(int
st = 1, ed = 1; ed < S/2;){
if(sum < S){
sum += ed;
ed++;
} else
if(sum == S) {
printf("Find a solution: %d %d\n", st, ed);
sum += ed;
ed++;
} else
{
sum -= st;
st++;
}
} |
这段代码的意思就是利用两个游标进行不断的逼近，终会找到所有的答案。
虽然这种方法简单，但是如果我们手边恰好没有电脑，我们应该怎么算？我们如何用笔算出答案呢？试试S=100。
前天看具体数学，偶然找到了一个非常棒的方法，这个方法怎么就没想到呢？
方法2：
那个方法大概是这个样子：
S=a + (a + 1) + (a + 2) + ...... + b = 1/2 * (a+b)(b-a+1)
2S=(a+b)(b-a+1)=xy
令 x=a+b,y=b-a+1，求得 a=(x-y+1)/2, b = (x+y-1)/2。
因为a,b肯定都是整数，所以有如下结论：x，y奇偶性互反，也就是说，若x是奇数，则y为偶数，若x为偶数，y则为奇数，否则a,b将不会是整数(能想明白么?)。
那么得到了这些信息又有什么用呢？有用，好戏来了。
由上面的结论可知，每一个x,y(满足x,y奇偶性不同)都会得到一个(a,b)对,所以不同的a,b的数目与2S的因子数有关系。那么接下来我们就要找出所有满足条件的x,y。
这个问题又回到了一个老生常谈的整数的质因子分解问题上了。
详情可参考另一篇博客（开灯关灯问题）,具体内容这里就不赘述了。下面直接来进行计算。
对2S进行质因数分解得：
2S=2^e[1]*p[2]^e[2]*......*p[m]^e[m]
那么，符合条件的x,y数目就是(e[2]+1)*(e[3]+1)*......*(e[m]+1),这里面没有用到e[1]是因为x,y其中一个是偶数，只要p[2]^e[2]*......*p[m]^e[m]的每个因子与2^e[1]相乘就会得到一个x,y。
接下来举个例子来说一下上面方法的过程吧！
S = 10
2S = 20 = (2^2)*5，所以满足S=a + (a + 1) + (a + 2) + ...... +
b的a,b有两组。因为a,b都大于0,所以x>y。
1: x = 5, y = 4 => a = 1 b = 4
即10=1+2+3+4
2: x = 20, y = 1 => a = 10
b= 10. 即10=10
S=15
2S=30=2*3*5，所以满足S=a + (a + 1) + (a + 2) + ...... + b的a,b有4组。
1:
x=6, y = 5 => a=1,b=5 即15=1+2+3+4+5
2: x=10,y = 3
=> a=4,b=6 即15=4+5+6
3: x=15,y = 2 => a=7,b=8
即15=7+8
4: x=30,y = 1 => a=15,b=15 即15=15
到现在为止，我们都限定x>y，这是由a,b>0推出来的，x-y=(a+b)-(b-a+1)=2a-1>0 => x > y。
假如我们不限制a,b必须都取正数会是神马样子的结果呢？那么很容易，只要调换x,y就会得到不一样的答案。
再拿S=10为例：
1: x = 4, y = 5 => a=0,b=4 即10=0+1+2+3+4
2: x = 1,
y = 20 => a=-9,b=10 即10=-9-8-7-......-1-0+1+2+3+......+9+10。
我想大家也看出规律来了，那么当S=15时，我们也很容易写出剩下的四种答案：
1: 15=0+1+2+3+4+5
2:
15=-1-2-3+0+1+2+3+4+5+6
3: 15=-6-5-4-3-2-1+0+1+2+3+4+5+6+7+8
4:
15=-14-13-......+0+1+2+......+14+15。
很简单的质因数分解能解决各种奇妙有趣的问题，真的很有意思。