题意
??给定半径r，求出圆
C：x2+y2=r2 在圆周上的整点数目
??r≤2?109
解法
枚举：
??设Y=y2,X=x2,R=r2
??则有：Y=R?X=(r+x)(r?x)······①
??令d=gcd(r+x,r?x),A=(r+x)/d,B=(r?x)/d
??∴gcd(A,B)=1,代入①式,得:
??Y=d2?A?B,易知A,B必须为完全平方数
??gcd(r+x,r?x)=gcd(r,x)或者gcd(r+x,r?x)=2?gcd(r,x)
??将所有可能的gcd(r,x)和2?gcd(r,x)记录下来,去重,记为d
∵B=(r?x)/d 为完全平方数，设B=k2
??∴x=r?k2?d
??求出x之后利用①求出y ，判断y是否是完全平方数即可
复杂度
??O（
n ），事实上要比O（n<script type="math/tex" id="MathJax-Element-1158">n</script>）小很多
代码
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define Rint register int
#define Lint long long int
using namespace std;
const int N=100010;
Lint q[N],r,ans;
Lint gcd(Lint a,Lint b) { return b ? gcd( b,a%b ) : a ; }
int main()
{scanf("%d",&r);int x=sqrt(r),c=0;for(int i=1;i<=x;i++){if( r%i!=0 ) continue ;q[++c]=i,q[++c]=2*i;if( i*i!=r ) q[++c]=r/i,q[++c]=2*r/i;}sort( q+1,q+c+1 );int tmp=c;c=0;for(int i=1;i<=tmp;i++){q[++c]=q[i];while( q[i+1]==q[c] && i+1<=tmp ) i++;}for(int i=1;i<=c;i++){Lint d=q[i];for(Lint k=1;k*k*d<=r;k++){Lint x=r-k*k*d;if( x<=0 ) continue ;if( gcd( r+x,r-x )!=d ) continue ;Lint w=r*r-x*x,y=sqrt(w);if( y*y==w ) ans++;}}printf("%d\n",ans*4+4);return 0;
}