解一道算法题

最近在学算法，看一本算法竞赛书，看到一定阶段来做算法题，随机抽了一道简单的coj 1132来做。

题目是求解一个数的所有除数组合出来的数之和(不包括自己)，比如：20 = 2 * 2 * 5，结果a(20) = 1 + 2 + 4 + 5 + 10 = 22。

首先我采用硬解的方法，求出所有的除数，然后排列组合一下。发现超时了。 回去看了一下题目，发现：测试用例数量equal to about 2*10^5，硬算的复杂度大概是n^3*log(n)，难怪算不出来，只能去优化算法了。

排列组合题目一般来说会有重合子问题，可以用动态规划来优化。先列出状态转移方程看看：

假设要求解a(n)，n可以拆分成除数d1, d2, … dk (dk > dk-1)，每个除数的数量是m1, m2, …, mk，那么a(n)结果和a(p)相关，其中p = d1^m1 * d2^m2 ... * dk-1^mk-1，拆分一下a(n)：

a(n) = sum( d1^s1 * d2^s2 * ... * dk-1^sk-1 * dk^sk ) (所有可能的 sk <= mk)
     = d1^m1 * ... * dk-1^mk-1 + sum( d1^s1 * ... * dk-1^sk-1 ) * dk^sk
     = p + a(p) * (1 + dk + dk ^ 2 + ... + dk ^ mk)
     = p + a(p) * (1 - dk^(mk+1)) / (1 - dk)
     

题目中进行了大量运算(n < 5*10^5 ，其中2/5的值都需要求解)，n利用到旧的p的概率很大， 又能够减少一个级别的复杂度，缓存a(p)的值到数组就可以了。

写程序的方法：每次计算a(n)都会先拆分除数列表，保存到一个vector数组里面。 然后调用a(p)，算出来的结果缓存到一个结果数组中。

之后进行优化：

• 发现其实不关心d1到dk-1的值，只需要dk就行了，mk可以循环除得到，那么只需要保存每个n最大的除数即可。

• 为了增加运行速度，求除数先维护一个素数数组，这样不用从2开始一个个除了。但是修改之后发现，计算素数数组的复杂度超了，反而不如原先算法快。

代码在这里。 我的答案时间消耗比最快的算法多将近一倍，不知道大家有什么更好的算法没有？

结论：

• 首先看清楚题目，包括：算法具体内容，示例是否符合自己猜想的算法，各个参数的范围。参数的范围算是一个坑，有一道算法题目是算a+b，然后没有给参数范围，无数人就栽在这上面，因为a和b是天文数字几百位。。

• 然后列出具体问题，寻找规律，列状态转移方程。空想比较慢，在纸上面看着一个实际问题方便寻找规律，验证算法正确性，以及考虑各种边界条件。

• 一定要计算复杂度。比如上面我打算先算素数优化执行效率，但是求素数的复杂度更高，优化后速度变慢了。

解算法题比CRUD有意思多了。