题目描述
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
输入格式：
r
输出格式：
整点个数
输入样例#1：
4
输出样例#1：
4
说明
n<=2000 000 000
题解：
以下来自http://blog.csdn.net/csyzcyj/article/details/10044629
【分析】：
样例图示：
首先,最暴力的算法显而易见：枚举x轴上的每个点，带入圆的方程，检查是否算出的值是否为整点，这样的枚举量为2*N，显然过不了全点。
然后想数学方法。
有了上面的推理，那么实现的方法为：
枚举d∈[1,sqrt(2R)]，然后根据上述推理可知：必先判d是否为2R的一约数。
此时d为2R的约数有两种情况：d=d或d=2R/d。
第一种情况：d=2R/d。枚举a∈[1,sqrt(2R/2d)] <由2*a*a < 2*R/d转变来>，算出对应的b=sqrt(2R/d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1
第二种情况：d=d。枚举a∈[1,sqrt(d/2)] <由2*a*a < d转变来>，算出对应的b=sqrt(d-a^2)，检查是否此时的A,B满足：A≠B且A,B互质 <根据上面的推理可知必需满足此条件>，若是就将答案加1
因为这样只算出了第一象限的情况<上面枚举时均是从1开始枚举>，根据圆的对称性，其他象限的整点数与第一象限中的整点数相同，最后，在象限轴上的4个整点未算，加上即可，那么最后答案为ans=4*第一象限整点数+4
【时间复杂度分析】：
枚举d：O(sqrt(2R)),然后两次枚举a：O(sqrt(d/2))+O(sqrt(R/d))，求最大公约数：O(logN)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL r, ans;
LL gcd(LL x, LL y)
{
return x%y == 0 ? y : gcd(y, x%y);
}
bool check(LL y, double x)
{
if (x == floor(x))
{
LL ls = (LL)floor(x);
if (gcd(ls*ls, y*y) == 1 && ls*ls != y*y)
return 1;
}
return 0;
}
int main()
{
scanf("%lld", &r);
LL ls = sqrt(2*r);
for (LL d = 1; d <= ls; d++)
{
if ((2*r)%d == 0)
{
for (LL j = 1; j <= (LL)sqrt(2*r/(2*d)); j++)
{
double b = sqrt(((2*r)/d)-j*j);
if (check(j, b))
ans++;
}
if (d != (2*r)/d)
{
for (LL j = 1; j <= (LL)sqrt(d/2); j++)
{
double b = sqrt(d-j*j);
if (check(j, b))
ans++;
}
}
}
}
printf("%lld", ans*4+4);
return 0;
}