同步考场上被卡常乐，有点难绷。
和题解不太一样，但是比较爆。
令 \(a=\frac yx,b=\frac zx\)，则：
\[a,b\in \Q,b^2+(a-1)b+1-a-a^2=0 \]这里的想法是解出有理数 \(b\)。有：
\[\Delta=\sqrt{5a^2+2a-3} \]那么 \(\sqrt{5a^2+2a-3}\in \Q\)。设 \(a=\frac cd,c,d\in \Z^+,c\bot d\)，得到：
\[\sqrt{(5c-3d)(c+d)}\in\Z \]注意到 \(\gcd((5c-3d),(c+d))\mid (5c-3d)+3(c+d)=8c\)，并且 \(\gcd((5c-3d),(c+d))\mid -(5c-3d)+5(c+d)=8d\)，那么
\[\gcd((5c-3d),(c+d))\mid (8c,8d)=8 \]弱化一下条件，可以设 \(c+d=2^{k_1}d_1^2,5c-3d=2^{k_2}d_2^2\)，其中 \(k_1=k_2\in \{0,1\},d_1,d_2\in \Z\)。然后消掉 \(k\)：
\[a=\frac cd=\frac{3d_1^2+d_2^2}{5d_1^2-d_2^2} \]解一下 \(b\)。
\[b=\frac{d_1^2-d_2^2\pm 4d_1d_2}{5d_1^2-d_2^2} \]那么可以得出原问题的解：
\[x'=5d_1^2-d_2^2,y'=3d_1^2+d_2^2,z'=d_1^2-d_2^2\pm 4d_1d_2 \]设 \(g=\gcd(x,y,z)\)，则 \(x=x'/g,y=y'/g,z=z'/g\)。
引理：若 \(d_1\bot d_2\)（显然只需要考虑这些）
\[(x,y)=(y,z)=(x,z)\in \{1,4\} \]类似于前面 \(\gcd((5c-3d),(c+d))\mid8\) 的证明即可。
那么：
\[3d_1^2+d_2^2=y'\le gn\le 4n \]所以 \(d_1,d_2=O(\sqrt n)\)。这样，我们枚举 \(d_1,d_2\) 就可以预处理 \(1\sim n\) 的所有答案。有点小小的卡常（当时我甚至求了 \(\gcd(x,y,z)\)）。
#include<bits/stdc++.h>
using namespace std;
inline int sqr(int x){return x*x;}
const int P=1.5e6;
inline int gcd(int a,int b){
while(max(a,b)>P){if(a<b)swap(a,b);if(!b)return a;a%=b;}
int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=min(az,bz),dif;
b>>=bz;
while(a){
a>>=az;
dif=b-a;
az=__builtin_ctz(dif);
if(a<b) b=a;
if(dif<0) a=-dif;
else a=dif;
}
return b<<z;
}
const int maxn=2e7+5;
int s[maxn],tmp;
inline int _max(int x,int y){return x>y?x:y;}
#define endl "\n"
signed main(){
int n=2e7;
for(int d1=0;d1*d1*3<=4*n;d1++){
int I=1;
if(d1>0&&d1%2==0)I=2;
bool s3=0,s5=0,s7=0;
if(d1>0&&d1%3==0)s3=1;
if(d1>0&&d1%5==0)s5=1;
for(int d2=1;d2*d2<=4*n-3*d1*d1&&d2*d2<=5*d1*d1;d2+=I){
if(s3&&d2>0&&d2%3==0)continue;
if(s5&&d2>0&&d2%5==0)continue;
int D1=d1*d1,D2=d2*d2;
if(d1>0&&d2>0&&gcd(d1,d2)>1)continue;
int x=5*D1-D2,y=3*D1+D2,z=D1-D2+4*d1*d2;
if(x>4*n||y>4*n||x<=0||y<=0||z<=0)continue;
int g=1;if(x%4==0)g=4;
x/=g,y/=g,z/=g;
if(x>n||y>n||z>n)continue;
s[_max(x,y)]++;
z=(D1-D2-4*d1*d2);if(z<=0)continue;
s[_max(x,y)]++;
}
}
for(int i=1;i<=n;i++)s[i]+=s[i-1];
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--){
int m;cin>>m;
if(m<=5){
//1 1 1
//5 3 1
if(m==1)cout<<1<<endl;
if(m==2)cout<<1<<endl;
if(m==3)cout<<1<<endl;
if(m==4)cout<<1<<endl;
if(m==5)cout<<2<<endl;
}else{
int dp=4;
if(m>=5)dp=1;
cout<<s[m]+dp<<endl;
}
}
return 0;
}
//From Koala