题目描述
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
输入输出格式
输入格式：
r
输出格式：
整点个数
输入输出样例
输入样例#1：
4
输出样例#1：
4
说明
n<=2000 000 000
接下来枚举d,a
为什么要除d？
因为他们不互质，a*b是完全平方数≠a,b都是完全平方数
记住还要a*a,b*b互质
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long r,k,ans,p,q;
int tot;
long long ys[];
void Dvide(long long x)
{int i;
for (i=;i<=sqrt(x);i++)
if (x%i==)
{
if (i*i==x)
{
tot++;
ys[tot]=i;
}
else
{
tot++;
ys[tot]=i;
tot++;
ys[tot]=x/i;
}
}
}
long long GCD(long long a,long long b)
{
if (b==)
return a;
return GCD(b,a%b);
}
int main()
{int i;
cin>>r;
Dvide(*r);
for (i=;i<=tot;i++)
{
for (p=;p*p<(r/ys[i]);p++)
{
q=sqrt(*r/ys[i]-p*p);
if (p*p+q*q==*r/ys[i])
if (GCD(p*p,q*q)==) ans++;
}
}
cout<<ans*+;
}