勾股三元组 solutions

算法 1

枚举 $a,b,c$ 并判断即可。

时间复杂度为 $O(n^3)$，能通过 easy version。

算法 2

枚举 $a,b$，判断 $\sqrt{a^2+b^2}$ 是否为 $\le n$ 的整数。

这可以变通成判断 $c=\lfloor\sqrt{a^2+b^2}\rfloor$ 是否满足 $c\le n$ 且 $a^2+b^2=c^2$。

时间复杂度为 $O(n^2)$，能通过 medium version。

算法 3

笔者原初的想法是这样的：

把 $a^2+b^2=c^2$ 变形成 $a^2=(c+b)(c-b)$。

枚举 $a$，根据 $a$ 的质因数分解枚举 $a^2$ 的约数 $d$，解 $\begin{cases}c-b=d\\c+b=\dfrac{a^2}{d}\end{cases}$ 并判断是否满足 $a\le b\le c\le n$。

求 $1,2,\cdots,n$ 的质因数分解可用欧拉筛预处理，对于每个 $a$ 还需把 $a^2$ 的约数排序。

时间复杂度为 $O\left(\sum\limits_{i=1}^n\mathrm{d}(i^2)\log\mathrm{d}(i^2)\right)\color{gray}{=O(n\log^2n\log\log n)}$，能通过 hard version。

算法 4

大多数同学都通过查阅资料或询问 AI 得到以下做法。

对于 $(a,b,c)$，记 $d=\gcd(a,b)$，若 $d>1$，称它由 $\left(\dfrac{a}{d},\dfrac{b}{d},\dfrac{c}{d}\right)$ 生成，例如 $(6,8,10)$ 由 $(3,4,5)$ 生成。称满足 $d=1$ 的 $(a,b,c)$ 为本原勾股三元组，考虑枚举它，生成 $(ka,kb,kc)$（$kc\le n$）。

下面考察本原勾股三元组 $(a,b,c)$ 的性质：

首先，$a,b$ 一奇一偶。$a,b$ 不可能均为偶数，而若 $a,b$ 均为奇数，则 $c^2$ 是 $2$ 的倍数但非 $4$ 的倍数，与 $c^2$ 是平方数矛盾。因此，可暂且忽略 $a,b$ 之间的大小关系，设 $a$ 是偶数，$b$ 是奇数，显然 $c$ 是奇数。

考察 $a^2=(c+b)(c-b)$，有 $\dfrac{c+b}{2},\dfrac{c-b}{2}$ 是互质的平方数：若不互质，设 $\gcd(c+b,c-b)=2d>2$，则 $2d\mid2b$，从而 $d\mid b$，$d\mid c$，$d\mid a$，矛盾！$\dfrac{c+b}{2},\dfrac{c-b}{2}$ 互质且乘积是平方数 $\dfrac{a^2}{4}$，根据质因数分解这两个数是互质的平方数。

设 $c+b=2x^2$，$c-b=2y^2$，满足 $\gcd(x,y)=1$，解得

另一方面，考虑枚举 $1\le y<x$ 满足 $\gcd(x,y)=1$ 且 $x^2+y^2\le n$，得到 $a,b,c$。此外，$x,y$ 的奇偶性要不同，否则 $b,c$ 是偶数。目前确有 $a^2+b^2=c^2$，还需证明 $\gcd(a,b)=1$：若不然，设 $\gcd(a,b)=d>1$，则 $d\mid b=x^2-y^2,c=x^2+y^2$，$d$ 是奇数且 $d\mid2y^2$，从而 $d\mid y^2$，$d\mid x^2$，与 $x^2,y^2$、$x,y$ 互质矛盾！

综上，我们得以精确地找出勾股数，只不过还需排序。根据算法 3 的思路和参考文章，勾股三元组个数的量级不高于 $O(n\log^2n)$。若直接一起排序，时间复杂度为 $O(n\log^3n)$，能通过 hard version。