首页 1 2 3 4 5 6 7

bzoj 1041[HAOI2008]圆上的整点 - 数论

1041: [HAOI2008]圆上的整点

Time Limit: 10 Sec Memory Limit: 162 MB

Description

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

Input

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

Output

整点个数

Sample Input

Sample Output

$ x ^ 2 + y ^ 2 = r ^2$

移项

$x ^ 2 = r ^ 2 - y ^ 2$

$x ^ 2 = (r - y) * (r + y)$

令 d = gcd(r - y, r + y)

设 $A = \frac{r - y}{d} = a ^ 2$, $B = \frac{r + y}{d} = b ^ 2$ (gcd(A , B) == 1)

则 $a ^ 2 + b ^ 2 = \frac{r * 2}{d}$

所以d 为 2 * r 的约数

再枚举 a = 1 ~ sqrt($\frac{d}{2}$) 即可

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #define LL long long
 7 
 8 using namespace std;
 9 
10 LL ans = 0;
11 LL r;
12 inline LL read()
13 {
14     LL x = 0, w = 1; char ch = 0;
15     while(ch < '0' || ch > '9') {
16         if(ch == '-') {
17             w = -1;
18         }
19         ch = getchar();
20     }
21     while(ch >= '0' && ch <= '9') {
22         x = x * 10 + ch - '0';
23         ch = getchar();
24     }
25     return x * w;
26 }
27 
28 int gcd(int a, int b)
29 {
30     if(b == 0) {
31         return a;
32     } else {
33         return gcd(b, a % b);
34     }
35 }
36 int main()
37 {
38     r = read();
39     for(int d = 1; d <= sqrt(2 * r); d++) {
40         if((2 * r) % d == 0) {
41             for(int a = 1; a < sqrt(2 * r / (2 * d)); a++) {
42                 int b = (int)sqrt(2 * r / d - a * a);
43                 if(b == sqrt(2 * r / d - a * a) && gcd(b, a) == 1) {
44                 //    cout<<a<<" "<<b<<endl;
45                     ans++;
46                 }
47             }
48             if(d != (2 * r) / d) {
49                 for(int a = 1; a < sqrt(d / 2); a++) {
50                     int b = (int)sqrt(d - a * a);
51                     if(b == sqrt(d - a * a) && gcd(b, a) == 1) {
52                 //        cout<<a<<" "<<b<<endl;
53                         ans++;
54                     }
55                 }
56             }    
57         }
58     }
59     ans = ans * 4 + 4;
60     printf("%lld\n", ans);
61     return 0;
62 }