随笔-14  评论-21  文章-0  trackbacks-0

这里先只考虑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!=0continue;
    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 阅读(2074) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理