Description
求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
Input
只有一个正整数n,n<=2000 000 000
Output
整点个数
Sample Input
4
Sample Output
4
Solution
数论题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll r; int ans; int gcd(int x,int y) { if (y==0) return x;else return gcd(y,x%y); } void calc(ll d) { for (int i=1;i<=sqrt(((ll)2*r/d)/2);i++) { ll j=sqrt(2LL*r/d-(ll)i*(ll)i); if (j==0) continue; if (gcd((ll)i,j)==1&&(ll)i*(ll)i+j*j==2LL*r/d) ans++; } } int main() { scanf("%lld",&r); ans=0; for (int i=1;i<=sqrt((ll)2LL*r);i++) if (2LL*r%(ll)i==0) { calc((ll)i); if ((ll)i*(ll)i!=2LL*r) calc(2LL*r/(ll)i); } printf("%d\n",ans*4); return 0; } |
