Project Euler前100题里程碑

最近花了一段时间做 Project Euler。做完前100题是一个重要的里程碑。100以后的题不允许公开发表题解，而且难度也急剧上升，估计包括我在内的很多人也没什么动力去做了。

1-50的题基本上没什么难度，可以作为编程初级训练，或者对一门新语言建立熟悉度的训练集。51-100的题难度稍有上升，而且个别题强烈依赖初等数论的结论，但总体来说还是很可做的。

大整数运算库在解 Project Euler 问题时特别有用。像16、97用大整数来算，几乎不用动任何脑筋。像Python, Haskell这样的语言，整数本身就是大整数，那就更方便了。

下面讨论几个我觉得比较有趣的主题，有很多是我头一次接触或者已经遗忘的知识。

零钱问题

第31题是一个经典的问题：求在给定面额硬币下，恰好凑出某个数值的方案数。通用的办法是动态规划：设f(k)为第k种面值，d(i,j)为“用前i种面值凑出j的方案数”。转移方程为 \[d(i,j)=d(i-1,j) + d(i-1, j-f(k)).\] 按先i后j的顺序枚举，可以把状态压缩为一维的。

类似的问题还有76、77，把“硬币”换成“全体自然数”或“全体质数”即可。

整数拆分

第76题求的是把整数拆分成整数之和的方案个数。这虽然也可以看作零钱问题，但是整数拆分是一个专门的研究课题，有特殊的解决方案：可以利用欧拉（不愧是Project Euler！）的五边形数定理更加高效地求解——计算$p(n)$所需时间为$O(n^{3/2})$。这是我第一次听说这个定理，对于78题所要求的问题规模特别有用。

整数边直角三角形（毕达哥拉斯三元组）

这里涉及到著名的欧几里得公式：对任意整数$m>n>0$，整数 \[a=m^2-n^2,\;b=2mn,\;c=m^2+n^2\] 构成直角三角形的三边。如果加上附加条件：1) m和n的奇偶性不同，2) m和n互质（即最大公约数为1，可用欧几里得算法求出），则以上公式给出所有的本原毕达哥拉斯三元组（a, b, c互质），对每个毕达哥拉斯本原三元组再枚举它的倍数，就可以不重不漏地枚举所有毕达哥拉斯三元组。

第39题是最早涉及整数边直角三角形的，但问题规模较小；第75题的规模较大。第86题和94题经过一定的数学推导，都可以化归为整数边直角三角形问题。（第94题的难度被标记为14，是前100题里最高的。）

Pell 方程

方程$$x^2 - Dy^2 = \pm1$$的整数解，和$\sqrt D$的连分式展开密切相关；这是初等数论中的一个著名结论。

第66题（难度为11，是前100题中第二高的）就直接让求解这个方程（得到解有几十位数字——用穷举的办法恐怕是不可行的）。第94题虽然可以用上一节提到的直角三角形的办法做，但也可以把问题转化为Pell方程来做，而且效率会更高。第100题需要进行一定的推导，得到一个Pell方程，然后求解。

题外话：AI和编程