第9题: 特殊勾股数
Problem 9: Special Pythagorean Triplet
题目
特殊勾股数
勾股数是满足以下条件的三个自然数：
$$a \lt b \lt c$$ $$a^2 + b^2 = c^2$$
例如 $3^2 + 4^2 = 9 + 16 = 25 = 5^2$。
只有一组勾股数满足 $a + b + c = 1000$。
找到这一组勾股数，并计算它们的积 $abc$。
Special Pythagorean Triplet
A Pythagorean triplet is a set of three natural numbers, $a \lt b \lt c$, for which,
$$a^2 + b^2 = c^2$$
For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.
There exists exactly one Pythagorean triplet for which $a + b + c = 1000$.
Find the product $abc$.
解题方法
暴力计算
直接从1到1000，遍历$a$、$b$、$c$，判断$a + b + c = 1000$是否成立。
公式法
查阅资料后可知任何勾股数均满足以下公式，其中$m>n$且$m$和$n$均为正整数：
$$ \begin{aligned} a&=m^2-n^2 \\ b&=2mn \\ c&=m^2+n^2 \end{aligned} $$
将上述公式代入$a + b + c = 1000$即可得到$m$和$n$与$1000$的计算公式。
$$ \begin{aligned} a+b+c&=1000 \\ m^2-n^2+2mn+m^2+n^2&=1000 \\ 2m^2+2mn&=1000 \\ m(m+n)&=500 \end{aligned} $$
观察公式可知$m$和$m+n$为$500$的因数，因此可从此处入手求解。
求解$500$的素因数可得
$$ 500=2^2*5^3 $$
根据$500$的素因数可以将此题求解过程转换为以下内容：
- $500$的所有素因数组成一个多重集合$\{2,2,5,5,5\}$，记作$S$
- 设$M$为$S$的非空子集,且$M\not =S$，则$m=\prod{M}$
- 设$N$为$M$针对$S$的补集，则$m+n=\prod{N}$
- $m>n>0$
最后通过遍历多重集合$S$的所有非空子集即可快速求解答案
| $M$ | $m$ | $N$ | $m+n$ | $n$ | $m>n>0$ |
|---|---|---|---|---|---|
| $\{2\}$ | $2$ | $\{2,5,5,5\}$ | $250$ | $248$ | false |
| $\{5\}$ | $5$ | $\{2,2,5,5\}$ | $100$ | $95$ | false |
| $\{2,2\}$ | $4$ | $\{5,5,5\}$ | $125$ | $121$ | false |
| $\{2,5\}$ | $10$ | $\{2,5,5\}$ | $50$ | $40$ | false |
| $\{5,5\}$ | $25$ | $\{2,2,5\}$ | $20$ | $-5$ | false |
| $\{2,2,5\}$ | $20$ | $\{5,5\}$ | $25$ | $5$ | true |
| $\{2,5,5\}$ | $50$ | $\{2,5\}$ | $10$ | $-40$ | false |
| $\{5,5,5\}$ | $125$ | $\{2,2\}$ | $4$ | $-121$ | false |
| $\{2,2,5,5\}$ | $100$ | $\{5\}$ | $10$ | $-95$ | false |
| $\{2,5,5,5\}$ | $250$ | $\{2\}$ | $10$ | $-248$ | false |
因此$m=20$、$n=5$，所以$a=375$、$b=200$、$c=425$，求解$abc$即可。