勾股数探究

勾股数，又叫毕达哥拉斯三元数， 是由正整数构成的三元组。其三个数对应一个直角三角形的三条边。
这里对勾股数的性质做一些探究。

基本性质

一般用一个三元组表示一组勾股数：$(a, b, c)$
其中有

$$a ^ 2 + b ^ 2 = c ^2$$

容易看出，一组勾股数中每一个数乘上一个正整数$n$，得到的三元组$(na, nb, nc)$仍为一组勾股数。
正因如此，我们希望找到这样的勾股数，使它不为除自己外某一个勾股数的倍数。换句话说，我们希望有一种方法可以枚举出所有的素勾股数，即使$(a, b, c)=1$。

构造方式

先直接给出这样的构造方式：
设$u < v(u ,v\in \mathbb{N}^*)$，并且$u,v$奇偶性不同，且$(u, v) = 1$，那么令

$$\begin{cases} a = v ^ 2 - u ^ 2\\ b = 2 u v \\ c = v ^ 2 + u ^ 2\end{cases}$$

即可构造出全部的素勾股数。
证明：
假设这样产生的勾股数存在$(a, b, c)= d$，那么由于$u, v$奇偶性不同， 故$a, c$必为奇数。故$d$为奇数。
则对于$c$则必须有$u|d, v|d$，导出$(u, v)\ge d$，与前提中的$(u, v)=1$矛盾。故原命题得证，证毕。

由此可见，使用这样的方式构造出素勾股数之后再进行倍增，即可构造出所有可能的勾股数。

问题扩展

问题：已知$a, b, c\in \mathbb{N}^*$和$b$，求满足$a ^ 2 + b ^ 2 = c ^ 2$的所有解。
解题：把式子化为$b ^ 2 = (c - a)(c + a)$，设$x = c + a, y= c - a$，那么就有$b ^2 = x y$。
对$b$枚举一次因数，然后对因数进行组合，同时考虑一下奇偶性带来的问题，计算出$x,y$，解出$a,c$即可。
因为因数的个数为$O(\sqrt b)$，组合因数的时候会产生$O(b)$的因数个数，所以该方法的时间复杂度应为$O(b)$。

相关运用

UVa106（同Poj1305）

---

参考资料

1. 《什么是数学》
2. 百度百科