题目大意：给定一个半径为为r的圆x^2+y^2=r^2，求圆上多少个点的坐标为整数

卡了很久的一道题。。。我之前用了两个公式，理论上可以O(√n)出解，可惜这两个公式并不能涵盖所有勾股数。。。

?

x^2+y^2=r^2

化简为 y^2=(r-x)(r+x)

我们令d=gcd(r-x,r+x)

则(r-x)/d与(r+x)/d一定互质，二者相乘为完全平方数，则二者一定都为完全平方数

令r-x=d*u^2,r+x=d*v^2

则有u,v互质，u

其中x=d(v^2-u^2)/2

y=d*u*v

r=d*(u^2+v^2)/2

枚举2r的因数d，对于每个d我们用O[√(r/d)]的时间枚举u 代入r的计算式得出v^2 计算v^2是否为完全平衡数及u与v是否互质

这样可以枚举出一个象限内的整点个数 然后输出(ans+1)*4即可

?

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; typedef long long ll; ll r,ans; ll factors[100100]; int tot; void Get_Factors(ll x) { ll i; for(i=1;i*i
       
        >r; int i; ll u; Get_Factors(r<<1); for(i=1;i<=tot;i++) { ll d=factors[i]; for(u=1;u*u<(r+1)/d;u++) { ll v_2=r*2/factors[i]-u*u; if( Is_Square(v_2) ) if(GCD(v_2,u*u)==1) ++ans; } } cout<<(ans+1<<2)<
        
         
?
         
?