这里先只考虑x，y都大于0的情况
如果x^2+y^2=r^2，则(r-x)(r+x)=y*y
令d=gcd(r-x,r+x),r-x=d*u^2,r+x=d*v^2,显然有gcd(u,v)=1且u<v
有2r=d*(u^2+v^2)，y=d*u*v，x=d(v^2-u^2)/2
枚举2r的约数d，再花费sqrt(2r/d)的时间枚举u，求出v=sqrt(2r/d-u^2)然后判断gcd(u,v)=1
最后结果乘以4（四个象限）+4（坐标轴上）即可
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int res;
int gcd(int a,int b)//·ÇµÝ¹éʵÏÖ
{
while(b) { int t=a%b; a=b; b=t; }
return a;
}
void solve(long long rr)
{
long long t;
int i,j;
for(i=1;(t=(long long)(i)*i)<=rr;i++)
{
j=int(sqrt(rr-t)+0.5);
if (i>=j) break;
if (t+(long long)(j)*j==rr&&gcd(i,j)==1)
res++;
}
}
int main(void)
{
int u,v,m,r,t;
long long rr,d;
scanf("%d",&r);
rr=r;
rr<<=1;
res=1;
for(d=1;(long long)(d)*d<=rr;d++)
{
if (rr%d!=0) continue;
solve(rr/d);
if ((long long)(d)*d==rr) break;
solve((long long)(d));
}
printf("%d\n",res<<2);
return 0;
}
posted on 2010-10-18 21:21
zxb 阅读(2072)
评论(0) 编辑 收藏 引用