【HAOI2008】圆上的整点
数学题
原题：
平面上有一个圆, 圆心坐标为(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<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 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<<ans*4+4<<endl; 26 return 0; 27 }