BZOJ 1041 [HAOI2008] 圆上的整点（数论）

本文主要是介绍BZOJ 1041 [HAOI2008] 圆上的整点（数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

Input
只有一个正整数n,n<=2000 000 000

Output
整点个数

Sample Input
4
Sample Output
4
Hint
科普视频

Source

太神了，竟然和素数扯上关系。
https://blog.csdn.net/csyzcyj/article/details/10044629

#include <cstdio>
#include <cstring>
#include <cmath>using namespace std;typedef long long ll;ll gcd(ll n,ll m)
{return m == 0 ? n : gcd(m,n % m);
}ll check(ll x,double y)
{if(floor(y) == y){ll yy = (ll)floor(y);if(gcd(x,yy) == 1 && yy * yy != x * x){return true;}}return false;
}int main()
{ll r;scanf("%lld",&r);ll ans = 0;for(ll d = 1;d <= sqrt(2 * r);d++){if((2 * r) % d == 0){for(ll a = 1;a <= sqrt((2 * r / (2 * d)));a++){double b = sqrt(((2 * r) / d) - a * a);if(check(a,b))ans++;}if((2 * r) / d != d){for(ll a = 1;a <= sqrt(d / 2);a++){double b = sqrt(d - a * a);if(check(a,b))ans++;}}}}printf("%lld\n",ans * 4 + 4);return 0;
}

这篇关于BZOJ 1041 [HAOI2008] 圆上的整点（数论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---