BZOJ 2190 仪仗队（欧拉函数）

题目连接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=47144

题意：求gcd(x, y) = 1, 0 <= x, y <= n的对数

思路：这题范围是从0开始的，所以，会多出(1, 0)和(0, 1)这两组，答案就是sigma(phi(i)) - 1 + 2。

code：

 1 #include <cstdio>
 2 #include <cstring>
 3 typedef long long LL;
 4 const int MAXN = 100005;
 5 
 6 LL phi[MAXN];
 7 int primes[MAXN];
 8 bool is[MAXN];
 9 int cnt;
10 
11 
12 void init()
13 {
14     phi[1] = 1L;
15     cnt = 0;
16     memset(is, false, sizeof(is));
17     for (int i = 2; i < MAXN; ++i) {
18         if (!is[i]) {
19             primes[cnt++] = i;
20             phi[i] = i - 1;
21         }
22         for (int j = 0; j < cnt && i * primes[j] < MAXN; ++j) {
23             is[i * primes[j]] = true;
24             if (i % primes[j] == 0) phi[i * primes[j]] = phi[i] * primes[j];
25             else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
26         }
27     }
28 }
29 
30 int main()
31 {
32     init();
33     int n;
34     while (scanf("%d", &n) != EOF) {
35         LL ans = 0;
36         --n;
37         for (int i = 2; i <= n; ++i) phi[i] += phi[i - 1]; 
38         ans += phi[n] * 2 + 1;
39         printf("%lld
", ans);
40     }
41     return 0;
42 }