首页 > 代码库 > BZOJ 1041 [HAOI2008]圆上的整点
BZOJ 1041 [HAOI2008]圆上的整点
1041: [HAOI2008]圆上的整点
Description
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
Input
只有一个正整数n,n<=2000 000 000
Output
整点个数
Sample Input
4
Sample Output
4
鸣谢：http://blog.csdn.net/csyzcyj/article/details/10044629 http://hzwer.com/1457.html
这么一到水题竟然卡了我一晚上，想起来确实是不可思议。
样例图示：
我们可以十分清晰的发现，这似乎就是一道算几题，但我们又很难下手。如果暴力枚举每个整数x，很明显会TLE。那怎么办呢？
右上图可知，我们可以枚举2*d的因数，这是O（sqrt(n)），再去枚举界的个数。因为此处前提为x>0,y>0,所以最后结果为ans*4+4。
因为涉及实数，所以屡调不顺，下次需多加注意。（floor一个实数结果仍为实数)
1 /************************************************************** 2 Problem: 1041 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:104 ms 7 Memory:828 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 long long n, ans; 13 inline long long gcd(long long a,long long b) {return b==0?a:gcd(b,a%b);} 14 int main() { 15 scanf("%lld",&n); 16 long long cou, b; 17 double t; 18 for( long long i = 1; i*i <= 2*n; i++ ) { 19 if(2*n%i==0) { 20 cou=i; 21 for( long long a = 1; 2*a*a < cou; a++ ) { 22 t=sqrt(cou-a*a); 23 if(t==floor(t)) { 24 b=(long long)floor(t); 25 if(a!=b&&gcd(a,b)==1) ans++; 26 } 27 } 28 cou=2*n/i; 29 if(2*n/i==i) continue; 30 for( long long a = 1; 2*a*a < cou; a++ ) { 31 t=sqrt(cou-a*a); 32 if(t==floor(t)) { 33 b=(long long)floor(t); 34 if(a!=b&&gcd(a,b)==1) ans++; 35 } 36 } 37 } 38 } 39 printf("%lld\n",ans*4+4); 40 return 0; 41 }
BZOJ 1041 [HAOI2008]圆上的整点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。