《编程之美》读书笔记25： 2.21只考加法的面试题
我们知道:
1+2 = 3；
4+5 = 9；
2+3+4 = 9。
等式的左边都是两个或两个以上连续的自然数相加，是不是所有的整数都可以写成这样的形式呢？
问题1： 对于一个64位正整数，输出它所有可能的连续自然数（两个以上）之和的算式。
问题2： 大家在测试上面程序的过程中，肯定会注意到有一些数字不能表达为一系列连续的自然数
之和，例如32好像就找不到。那么，这样的数字有什么规律呢？能否证明你的结论？
问题3： 在64位正整数范围内，子序列数目最多的数是哪一个？
假设自然数n可以拆分成：m, m+1, …, m+k-1 （m >= 1, k >= 2 ）
则 n = (m + m+k-1)*k/2 即 2*n = (2*m+k-1)*k
由于(2*m+k-1)与k的奇偶性是相反的，因此，可以先将n的所有质因子2提取出来，得到：
2 * n = 2^t * a * b，由于(2*m+k-1)与k的奇偶性相反，且(2*m+k-1) > k，当确定了a，b时，
可得到2*n的两组拆分(2^t * a, b) 和 (a, 2^t * b)（当a等于b时，这两组拆分是一样的），对每组拆分，k是较小的数。
对问题一：
最高效的解决方法是：找出2*n的所有质因子，然后再组合这些质因子。
可以用一个队列保存前m个因子的组合结果。（该队列所用的内存并不大。）
另见： 输出和为n的所有的连续自然数序列 输出自然数n的所有因子
对问题二：
要使n不能拆分，则说明两组拆分 (2^t * a, b) 和 (a, 2^t * b)都不能存在。
因而 min(2^t * a, b) < 2， min(2^t * b, a) < 2 （即都不满足k值>=2）
因而 b < 2 且 a < 2 即 a = b = 1， n = 2^(t-1)
因而： 当n等于2的t次幂时，n不能被拆分。
对问题三：
显然，拆分个数，只与奇质因子的数目有关。
2 ^ 64 = 1.8e19
3 * 5 *7 *11 *13 *17 * 19 *23 *29 *31 * 37 *41 * 43 *47 *53 = 1.6e19
假设N是有最多因子个数的最小64位奇数，设 N = 3^a3 * 5^a5 * 7^a7 …
则一定有 a3 >= a5 >= a7 … 否则只要交换不满足条件的那两个数，得到相同因子个数但比N更小的数，这与假设矛盾。
S = 2 ^ 64 = 1.8e19
M=3*5*7*11*13*17*19*23*29*31*37*41*43*47*53=1.6e19（因子个数2^15）
因而，N的最大质因子一定小等于53
由S / (M / 53) = 60 可将60拆分成3^3（因子数5*2^13） 3^2 * 5（因子数3*2^14）
可得局部最优解：R1 = 3^3 *5^2 *7*11*13*17*19*23*29*31*37*41*43*47
如果N不等于R1，则a47 = 0（要将S / (M / 53/47)) = 2820 拿出来拆分）
若N包含k个质因子a， t为满足a^t > 47（显然t >= 2）的最小整数，则 k < 2*t-1
（否则若将t个a拆分成47，由 (k+1)*1 – (k-t+1) * 2 = 2*t-k-1 <=0，
可知拆分后得到的数更优，与N最优矛盾）。
因此a3 <=2*4-2=6，
a5 <= 2*3 – 2 = 4,
a7 <= 2*2-2 = 2
a11 <= 2*2-2 = 2
若a7 <=1， 则a3<=4，否则可以将2个3拆成1个7，得到更优解。由
S/(3^4*5^4)/ (7*11*13*17*19*23*29*31*37*41) = 35
（能得到的最多因子个数为25*2^10 < 3*2^14不是最优解）
因而 a7 = 2
（ 若az = 2, ax = a, ay =b 且 z > x * y，若不能将 z拆分成 x * y，则有
(a+1)*(b+1)*3 > (a+2)*(b+2)*2，即 (a-1)*(b-1) >= 7 ）
若a23=2则可将1个23拆成3和7，由 (1+a3)*3*3 – (1+a3+1)*4*2 = a3-7<0
可知得到的数更优，与假设矛盾，因而 a23<=1，
由于 S/(3^6*5^4)/(7*11*13*17*19)^2 = 387 > 23因而 一定含有因子23，a23 = 1
若a31=0，则 a5 = 2（否则，5*7合并成31，得到更优解）
由 2^64 / (3^6*(5*7*11*13*17*19)^2 * 23 * 29) = 14
可知，该情况下得到的最大数不是最优， 因而 a31 = 1
（若a17 =2则 a3>=5, a5=3 或 a3>=4 a5=4，否则可以将17拆分成3*5）
利用前面的结论，
a3 >= a5 >= a7 …
a3 <= 6 a5 <= 4 a7 = 2 a23 = 1 a31 = 1 a47 = 0
可在较短时间内搜索出满足上述条件的因子个数最多的奇数，再与局部最优解R1进行比较，就可以确定最优解。
作者： flyinghearts
出处： http://www.cnblogs.com/flyinghearts/
本文采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议进行许可，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。