定义 ，即 共轭。
枚举 ，计算 。。
求出 分解成一对共轭复数之积的方案，再去重即可。
考虑将 质因数分解：
（ 即 非高斯质数， 即 为高斯质数）
注意到费马平方和定理，。把所有因子分成 两部分使得两部分之积共轭，分别考虑 对 的分配情况。
，，有分配方案使得 对 的分配情况为：
| 个 | 个 | |
| 个 | 个 |
无法再分，只能将 个 分配给 ，将 个 分配给 。处理出所有分配情况即可。
代码：
#include<bits/stdc++.h>
using namespace std;
inline void write(int a, int b, int c)
{
cout<<a<<' '<<b<<' '<<c<<'\n';
}
int n,c;
pair<int,int> q[5000050];
complex<double> f[1000050];
vector<complex<double>> v[2];
int main()
{
cin>>n;
for(int i=1;i*i<=n;++i)
for(int j=i+1;i*i+j*j<=n;++j)
f[i*i+j*j]=i*1.0+j*1.0*1i;
for(int z=1,a,o=0;z<=n;++z)
{
a=z;
vector<complex<double>>().swap(v[o]);
v[o].push_back(1);
for(int p=2,k;p*p<=a;++p)
if(!(a%p))
{
k=0;
while(!(a%p))
a/=p,++k;
vector<complex<double>>().swap(v[o^=1]);
if((p&3)!=1)
{
complex<double> C=pow(p, k);
for(auto V:v[o^1])
v[o].push_back(V*C);
}
else
for(int i=0;i<=(k<<1);++i)
{
complex<double> C=pow(f[p],i),D=pow(conj(f[p]),(k<<1)-i);
for(auto V:v[o^1])
v[o].push_back(V*C*D);
}
}
if(a!=1)
{
vector<complex<double>>().swap(v[o^=1]);
if((a&3)!=1)
for(auto V:v[o^1])
v[o].push_back(a*1.0*V);
else
for(int i=0;i<=2;++i)
{
complex<double> C=pow(f[a],i),D=pow(conj(f[a]),2-i);
for(auto V:v[o^1])
v[o].push_back(V*C*D);
}
}
for(auto V:v[o])
{
int x=abs(V.real()),y=abs(V.imag());
if(x>y) swap(x,y);
if(x) q[c++]={x,y};
}
}
sort(q,q+c);
c=unique(q,q+c)-q;
for(int i=0;i<c;++i)
write(q[i].first,q[i].second,abs(q[i].first*1.0+q[i].second*1.0*1i));
return 0;
}