【解题思路】
先只考虑第一象限与x轴正半轴，则x>0,y≥0，x2+y2=r2<=>x2=r2-y2=(r+y)(r-y)
设A=r+y,B=r-y，原式即：x2=AB。
设g=(A,B)，则设a=A/g，b=B/g，显然(a,b)=1。
于是原式即：x2=abg2，又(a,b)=1，则a,b均为完全平方数。
又A+B=g(a+b)=2r，则g必为2r的因数。
由此，我们可以枚举2r的因数g，对于每个g，我们不妨假定a<b，枚举√a∈[1,√(g/2)]统计即可。
然后推广到整个平面就是第一象限的统计量乘4。复杂度不紧确上界O(d(r)√(r)log2r)。
【参考代码】
1 #include<cstdio> 2 #include<cmath> 3 #define REP(I,start,end) for(int I=start;I<=end;I++) 4 #define sqr(n) n*n 5 using namespace std; 6 int gcd(int x,int y) 7 { 8 if(x%y==0) 9 return y; 10 return gcd(y,x%y); 11 } 12 inline long long work(int i) 13 { 14 long long result=0ll; 15 REP(j,1,sqrt(i>>1)) 16 { 17 int B=i-sqr(j),k=sqrt(B); 18 result+=sqr(k)==B&&gcd(j,k)==1; 19 } 20 return result; 21 } 22 long long r; 23 int main() 24 { 25 scanf("%lld",&r); 26 r<<=1; 27 long long ans=0ll; 28 REP(i,1,sqrt(r)) 29 if(r%i==0) 30 { 31 ans+=work(i); 32 ans+=work(r/i); 33 } 34 printf("%lld\n",ans<<2); 35 return 0; 36 }
原文：http://www.cnblogs.com/spactim/p/6505489.html
