本题做法很多，如果你想到了$O(n)$的做法，可以练习出题人DengDuck

邮箱：moudengya123@qq.com

这可以让DengDuck出更强的数据，同时在加强版的题面上也会感谢您

简化题意

大家都知道勾股定理吧，对于一个直角三角形，两直角边平方之和等于斜边的平方

式子表示为$a^2+b^2=c^2$

其实还有一个勾股逆定理，若三角形满足$a^2+b^2=c^2$，三角形为直角三角形

所以本题可以理解为

已知正整数$n$,求

$$\begin{cases} x^2+y^2=z^2\\ x<y<z \leq n \end{cases} $$

的所有正整数解

$\mathcal O(n^3)$做法

直接枚举$x,y,z$,判断是否符合上述式子

这样显然超时

$\mathcal O(n^2)$做法

可以枚举$x,y$,然后判断对应的$z$是不是平方数（平方根是不是整数）

稍微快一点，

$\mathcal O(\dfrac {n^2} {\log n})$ 做法

$$x^2+y^2=z^2 \\ x^2=z^2-y^2 \\ x^2=(z+y)(z-y)\\ \because z>0,y>0 \\ \therefore z+y>z-y $$

考虑对$x^2$分解成$x^2=ab$,其中$a>x>b>0$且为正整数 得二元一次方程组

$$\begin{cases} z+y=a\\ z-y=b \end{cases}$$

解得

$$\begin{cases} z=\frac{a+b}2\\ y=\frac{a-b}2 \end{cases} $$

所以有一个要求

$$a \equiv b (mod\; 2)$$

才能使$z,y$为整数

对于每一个$x$,求出$a,b$,判断以上注意事项即可

如何分解

如果直接分解$x^2$,需要枚举$1$~$x$,复杂度太高了，我们需要简单的$O(\sqrt{x})$做法

可以分解$x$,在推广到$x^2$

memset(cnt,0,sizeof(cnt));
		long long k=x;
		for(int j=2;j<=k;j++)
		{
			if(k%j==0)
			{
				cnt[0][0]++;
				cnt[cnt[0][0]][0]=j;
				while(k%j==0) 
				{
					cnt[cnt[0][0]][1]++;
					k/=j;
				}
				cnt[cnt[0][0]][1]*=2; //to be x^2
			}
		}

时间复杂度为 $\mathcal O(\dfrac {n^2} {\log n})$