1041: [HAOI2008]圆上的整点

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 5059 Solved: 2302
[Submit][Status][Discuss]

Description

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

Input

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

Output

整点个数

Sample Input

Sample Output

HINT

科普视频

参考csyzcyj前辈题解

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 
 6 #define LL long long
 7 #define sqr(x) ((x)*(x))
 8 
 9 LL r,ans;
10 
11 LL gcd(LL a,LL b)
12 {
13     return b?gcd(b,a%b):a;
14 }
15 
16 bool check(LL a,double b)
17 {
18     if(b==floor(b))
19     {
20         LL x=(LL)floor(b);
21         if(gcd(sqr(x),sqr(a))==1&&x!=a)
22             return true;
23     }
24     return false;
25 }
26 
27 int main()
28 {
29     cin>>r;
30     for(LL d=1;d<=(LL)sqrt(2*r);d++)
31         if((2*r)%d==0)
32         {
33             for(LL a=1;a<=(LL)sqrt(r/d);a++)
34             {
35                 double b=sqrt(2*r/d-sqr(a));
36                 if(check(a,b))
37                     ans++;
38             }
39             if(d!=2*r/d)
40                 for(LL a=1;a<=(LL)sqrt(d/2);a++)
41                 {
42                     double b=sqrt(d-sqr(a));
43                     if(check(a,b))
44                         ans++;
45                 }
46         }
47     cout<<ans*4+4<<endl;
48     return 0;
49 }