自动搬运

查看原文

来自洛谷，原作者为

	p878567 以下证明：这一算法的时空复杂度是 $o(+\infty)$

搬运于2025-08-24 21:22:30，当前版本为作者最后更新于2017-12-30 15:35:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有一种特殊的思路：（证明$n>=4$时，$b=4k$）。

过程：设$p=a^2+b^2$。

1.$a,b$为偶数。设$a=2m,b=2n$，则$p=4(m^2+n^2)$。

2.$a,b$一奇一偶。不妨令$a=2m+1,b=2n$，则$p=4(m^2+n^2+m)+1$.

3.$a,b$为奇数。设$a=2m+1,b=2n+1$，则$p=4[m(m+1)+n(n+1)]+2$.

由于$m,m+1$中有$1$个偶数，故$m(m+1)$为偶数，同理，$n(n+1)$为偶数，即$m(m+1)+n(n+1)$为偶数，有$p=8l+2\text{（}l\text{为自然数）}$.

即$p\bmod 4\neq 3$.

即$n>=4$时，$b$为偶数.

若$4\nmid b$，则$a$为偶数。由于能写成$8l+6$的形式的数无法写生两个完全平方数的和（$8l+6=4(2l+1)+2$，即能$8l+6$写成$4l+2$的形式，但已证能写成$4l+2$形式的数一定不是完全平方数），故$a$为奇数，矛盾。

即$4\mid b$。

直接搜索，$b$要$4$个$4$个加（n=3时暴力搜索，有答案不超过$10000$个的限制，因此$m$很小）。