题解 CF1487D 【Pythagorean Triples】

来一发纯数学做法。 $c=a^2-b$ $a^2+b^2=(a^2-b)^2=a^4-2a^2b+b^2$ $a^4-(2b+1)a^2=0$ $a^2-2b-1=0$ $b=\frac{a^2-1}{2}$ $c=a^2-\frac{a^2-1}{2}=\frac{a^2+1}{2}\leq n$ $\left\{ \begin{aligned} 1\leq \frac{a^2+1}{2}\leq n \\ 1\leq \frac{a^2-1}{2}\leq n \\ 1\leq a\leq n \\ \end{aligned} \right. $ 解得 $\sqrt{3}\leq a\leq\sqrt{2n-1}$。 注意到 $a,b,c$ 均为正整数，因此 $2|a^2-1$ 推出 $2\nmid a$。 因此答案为 $\sqrt{3}\leq a\leq\sqrt{2n-1}$ 范围内的所有奇数，即 $1\leq a\leq\sqrt{2n-1}$ 奇数数量 $-1$。 因此直接统计就好了，$O(1)$ 得出答案。 ```cpp #include<iostream> #include<cstdio> #include<cmath> using namespace std; long long t,n; int main() { scanf("%lld",&t); while(t--) { scanf("%lld",&n); printf("%lld\n",((long long)(sqrt((n<<1)-1))-1)>>1); } return 0; } ```