求x2+y2=r2的整数解个数，显然要化化式子。考虑求正整数解。
y2=r2-x2→y2=(r-x)(r+x)→(r-x)(r+x)为完全平方数→(r-x)(r+x)/d2为完全平方数，d=gcd(r-x,r+x)→(r-x)/d·(r+x)/d为完全平方数，gcd((r-x)/d,(r+x)/d)=1→(r-x)/d和(r+x)/d均为完全平方数→(r-x)/d+(r+x)/d=2r/d为整数，即d|2r
于是我们可以以√n的复杂度枚举d，然后枚举√(r-x)/d，检验一下是否满足之前推导中的条件即可，再加上坐标轴上和其余象限的答案。
这样的复杂度并不显然，不过感觉上明显低于线性，并且一个数的因数个数是有比较优秀的上界的：n1.066/ln(ln n)。http://vfleaking.blog.163.com/blog/static/174807634201341913040467/
还有O(分解质因数)的神仙做法，似乎将素数拓展到了复平面，并不可能懂。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define ll long longint n,ans=0;ll m;ll gcd(ll n,ll m){ return m==0?n:gcd(m,n%m);}void solve(ll x){ if (x>=n) return; for (int i=1;i*i*x<=n;i++) { int a=i*i; if (gcd(a,m/x-a)==1&&((ll)sqrt(m/x-a))*((ll)sqrt(m/x-a))==m/x-a) ans++; }}int main(){#ifndef ONLINE_JUDGE freopen("bzoj1041.in","r",stdin); freopen("bzoj1041.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read();m=1ll*n<<1; for (ll i=1;i*i<=m;i++) if (m%i==0) { solve(i); if (i*i