勾股数的归纳与整理
Take_A_Single_6
·
·
算法·理论
我们称正整数三元组 (a,b,c) 为一组勾股数当且仅当 a^2+b^2=c^2。求所有勾股数最显然的做法就是 O(n^3) 枚举，那我们有没有更快的做法呢？
我们可以进行如下推导：
b^2 = c^2-a^2 = (c+a)(c-a),
令 x = c+a,y = c-a 得到：
a= \frac{x-y}{2},b=\sqrt{xy},c= \frac{x+y}{2},
再令 m= \sqrt{\frac{x}{2}},n=\sqrt{\frac{y}{2}} 得到：
a=m^2-n^2,b=2mn,c=m^2+n^2.
- 若 $a$ 奇 $b$ 偶，则 $m,n$ 必为整数
证明：
$$\begin{aligned}
& \because a\text{ 为整数}\\
& \therefore x,y\text{ 奇偶性相同}\\
& 又\because b\text{ 为偶数}\\
& \therefore x,y\text{ 均为偶数}\\
& \because a,c\text{ 互质}\\
&\begin{equation}
\therefore \frac{x-y}{2}\text{ 与 }\frac{x+y}{2}\text{ 互质}
\end{equation}\\
& \text{设 }\frac{x}{2}\text{ 与 }\frac{y}{2}\text{ 存在公因数 }d\\
& \therefore \frac{x}{2} = k_1d,\frac{y}{2}=k_2d (k_1,k_2\in\mathbb{Z})\\
& \therefore \frac{x-y}{2}=(k1-k2)d,\frac{x+y}{2}=(k1+k2)d\text{ 存在公因数 }d\text{ 与(1)矛盾}\\
& \therefore \frac{x}{2},\frac{y}{2}\text{ 互质}\\
& 又\because b\text{ 为整数}\\
& \therefore xy\text{ 为完全平方数}\\
& \therefore \frac{x}{2}\text{ 与 }\frac{y}{2}\text{ 为完全平方数}\\
& \therefore m,n\text{ 为整数}
\end{aligned}$$
- 若 $a$ 偶 $b$ 奇，则 $m,n$ 显然不均为整数
所以枚举合法的 $m,n$ 能使所有本原勾股数恰好出现一次，以所有本原勾股数构造 $(ka,kb,kc)$ 得到所有勾股数。枚举本原勾股数是 $O(\sqrt{n}\cdot\sqrt{n})$，加上枚举 $k$ 调和级数总复杂度 $O(n\log n)$。
```cpp
for(int i=0;i*i<n;i++)
for(int j=i+1;j*j-i*i+2*i*j<n;j++)
if(__gcd(j*j-i*i,2*i*j)==1)
for(int k=1;k*(j*j-i*i+2*i*j)<n;k++)
x=k*2*i*j,y=k*(j*j-i*i),z=k*(j*j+i*i);
```