[haoi2008]圆上的整点

很迷的一道题，你得有强硬的数学基础以及贼强的判断力才行；

题解来自黄学长博客QAQ

Description

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。

Input

r

Output

整点个数

Sample Input

4

Sample Output

4

HINT

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<cstring>
#include<cmath>
using namespace std;
long long gcd(long long x,long long y){return x%y==0 ? y : gcd(y,x%y);}  
int  check(long long y,double x)  
{  
      if(x==floor(x))//判断整点   
      {  
		long long x1=(long long)floor(x);//x1*x1必定是大于y*y的；
		if(gcd(x1*x1,y*y)==1 && x1*x1!=y*y)//gcd(A,B)=1并且A!=B   
			return 1;  
      }  
      return 0;  
} 
long long ans=0;
int main()
{
	long long r;
	cin>>r;
	for(long long  d=1;d*d<=r*2;d++)
	{
		if((2*r)%d==0)
		{
			for(long long  a=1;a*a<=2*r/(2*d);a++)
			{
				double b=sqrt(1.0*2*r/d-a*a);
					ans+=check(a,b);				
                          
			}
			if(2*r/d!=d)
			{
				for(long long a=1;a*a<=d/2;a++)
				{	
					double b=sqrt(1.0*d-a*a);
                        ans+=check(a,b);
				}	
			}
		}
	}
	cout<<ans*4+4<<endl;
	return 0;
}