数学题

原题：

平面上有一个圆, 圆心坐标为(0,0),半径为n. 问圆周上有多少个整点. 整点的定义即x,y坐标均为整数的点。

 

这根本就是一道数学题，注意是数学题，不是数论，数学！

纯粹就看魔性变公式的能力了

一种写法是酱紫的->http://blog.csdn.net/csyzcyj/article/details/10044629

黄学长的博客上也是这个，然而这个有点复杂啊我这么弱不会啊

然后就看到了一个比较简便的，我这种数学撑死了考不过120的弱鸡也能玩出来的方法

（只是看题解推出来，自己想出来这种东西怎么可能做到

直接上公式

x^2+y^2=r^2

x^2=r^2-y^2

　　=(r+y)(r-y)

设d=gcd(r+y,r-y), r+y=d*U, r-y=d*V

因为y≠0, 所以U≠V

因为d^2*U*V=x^2, 所以可设U=u^2, V=v^2

r+y=d*u^2, r-y=d*v^2

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

显然有gcd(u,v)==1 且 u<v

所以枚举d，再枚举u^2（枚举的时候要保证u是整数），计算出v（同时也要保证v是整数且u<v）

看一下gcd(u,v)是否的等于1即可

再深的证明我也不会了

数学题= =

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define ll long long 8 ll gcd(ll x,ll y){  return y?gcd(y,x%y):x;} 9 ll n;  ll n2;10 ll ans=0;11 void cclt(ll x){12     ll y=n2/x,j;13     for(ll i=1;i*i<=y;++i){14         j=(int)(sqrt(y-i*i*1.0)+0.5);15         if(i>=j)  break;16         ans+=(j*j==y-i*i & gcd(i,j)==1);17     }18 }19 int main(){
    //freopen("ddd.in","r",stdin);20     cin>>n;  n2=n<<1;  ll N=(ll)sqrt(n*2.0);21     for(ll i=1;i<=N;++i)if(!(n2%i)){22         cclt(i);23         if(i*i!=n)  cclt(n2/i);24     }25     cout<
           
            <