勾股数的归纳与整理

勾股数的归纳与整理

Take_A_Single_6

·

2024-09-22 09:43:14

·

算法·理论

我们称正整数三元组 (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

for(int j=i+1;j*j-i*i+2*i*j

if(__gcd(j*j-i*i,2*i*j)==1)

for(int k=1;k*(j*j-i*i+2*i*j)

x=k*2*i*j,y=k*(j*j-i*i),z=k*(j*j+i*i);

```