Once edited 4 年前
对于任意的$c, c\in N^+$, 求出所有的有序数对$(a, b)$, $a, b\in N^+$满足$a^2+b^2=c^2$
直接求解难以入手，我们考虑把$a^2$移项，得到$b^2=(c+a)(c-a)$
因为$c+a$和$c-a$是一个完全平方数的两个因子，我们考虑其最大公因数。令$d=(c+a, c-a)$，设$c-a=Ud$，$c+a=Vd$，那么$b^2=UVd^2$。因为$(U,V)=1$，所以得到$U$和$V$均为完全平方数。
因此，令$U=u^2$，$V=v^2$，得到$b^2=u^2v^2d^2$，$c-a=u^2d$，$c+a=v^2d$。
后两式相加消去$a$，得到$u^2+v^2=\dfrac{2c}{d}$。至此我们已经可以解决该题。
首先枚举$d$，因为$d|2c$，所以枚举$d$的复杂度是$O(\sqrt{c})$。接着我们枚举$u$（鉴于$u < v$，我们枚举$u$而不是$v$）。枚举$u$的时间复杂度为$O(\sqrt{d})$。
接下来我们考虑如何求出$a$和$b$。$b=uvd$可以直接求出。至于$a$，我们把$c-a=u^2d$，$c+a=v^2d$两式相减，得到$a=\dfrac{v^2-u^2}{2d}$。
最后我们需要对枚举结果进行筛选。我们需要保证$(u,v)=1, u^2+v^2=\dfrac{2c}{d} $。
总时间复杂度为$O(\sum_{d|c}\sqrt{d})$，可以通过所有测试点。