1041: [HAOI2008]圆上的整点
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4210 Solved: 1908
[Submit][Status][Discuss]
Description
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
Input
只有一个正整数n,n<=2000 000 000
Output
整点个数
Sample Input
4
Sample Output
4
HINT
Source
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1041
【分析】：
样例图示：
首先,最暴力的算法显而易见：枚举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)
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline ll read() 5 { 6 ll x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 { 10 if(ch=='-') 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 { 16 x=x*10+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 inline void write(ll x) 22 { 23 if(x<0) 24 { 25 putchar('-'); 26 x=-x; 27 } 28 if(x>9) 29 { 30 write(x/10); 31 } 32 putchar(x%10+'0'); 33 } 34 ll gcd(ll a,ll b) 35 { 36 return b==0?a:gcd(b,a%b); 37 } 38 inline bool check(ll y,double x) 39 { 40 if(x==floor(x))//判断整点 41 { 42 ll x1=(ll)floor(x); 43 if(gcd(x1*x1,y*y)==1&&x1*x1!=y*y)//gcd(A,B)==1&&A!=B 44 return true; 45 } 46 return false; 47 } 48 int main() 49 { 50 ll R; 51 R=read(); 52 ll ans=0; 53 for(ll d=1;d<=(ll)sqrt(2*R);d++)//1<=d^2<=2R 54 { 55 if((2*R)%d==0) 56 { 57 for(ll a=1;a<=(ll)sqrt(2*R/(2*d));a++)//2*a^2<2*R/d 58 { 59 double b=sqrt(((2*R)/d)-a*a); 60 if(check(a,b)) 61 ans++; 62 } 63 if(d!=(2*R)/d) 64 { 65 for(ll a=1;a<=(ll)sqrt(d/2);a++)//2*a^2<=d 66 { 67 double b=sqrt(d-a*a); 68 if(check(a,b)) 69 ans++; 70 } 71 } 72 } 73 } 74 printf("%lld\n",ans*4+4); 75 return 0; 76 }
