求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。r<=2000
000 000
这道题刚看时，就明白暴力不能解决一切。要是r^2<=20亿,还可以sqrt循环，这样的话只能用数学方法了。
（嘘！本数学方法的关键一步是借鉴来的）
x^2+y^2=r^2
x^2=r^2-y^2
x^2=(r+y)(r-y)
我们设gcd(r+y,r-y)=d //不知道什么是GCD？就是最大公因数
再设m=(r+y)/d,n=(r-y)/d，易得gcd(m,n)=1
因为m*n=x^2/d/d，即m*n是平方数。
又因为m和n互质，所以它们分别是平方数，我们还可以设m=u^2,n=v^2 。
带回去，r+y=d*u^2,r-y=d*v^2。
两式相加，2r=d(u^2+v^2)
加到这里，这些字母都表示整数。
现在我们的目标达成了:即把r^2降成了r。
我们可以枚举sqrt（2r），再依次判断是否有整数的u,v，且它们是否互质 。
最后还要注意以下:首先，所得结果要乘4 ，比如(3,4),还有(3,-4),(-3,4),(-3,-4)。
当然，如果x=0或y=0是一定可以的。最后还要加上4,即(0,r),(r,0),(0,-r),(-r,0)。（呵呵，r不等于0,O(∩_∩)O~~）
以下附代码：
#include<cstdio>
#include<cmath>
using namespace std;
const double jing=0.00000001;
long gcd(long a,long b){if (a%b==0) return b;return gcd(b,a%b);}
long long ans=0,r,temp;long i,j;double t;
int main()
{
scanf("%lld",&r);r*=2;
for (i=1;i<=trunc(sqrt(r));i++)
if (r%i==0)
{
temp=r/i;
for (j=1;j<=trunc(sqrt(temp));j++)
{
t=trunc(sqrt(temp-j*j));if (t<=j) break;
if (t*t+j*j==temp){if (gcd(j,t)==1) ans++;}
}
if (r/i==i) continue;temp=i;
for (j=1;j<=trunc(sqrt(temp));j++)
{
t=trunc(sqrt(temp-j*j));if (t<=j) break;
if (t*t+j*j==temp){if (gcd(j,t)==1) ans++;}
}
}
ans*=4;ans+=4;printf("%ld",ans);
return 0;
}