HDU 2841 Visible Trees（莫比乌斯反演）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2841

题意：给n*m的矩阵（从(1,1)开始编号）格子，每个格子有一棵树，人站在（0,0）的位置，求可以看到多少棵树。同一直线上的树只能看到最靠近人的那颗。

思路：可以将题目转化为求gcd(x, y) = 1，(1 <= x <= n, 1 <= y <= m)的对数。直接套用莫比乌斯反演即可。

code：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 const int MAXN = 1000005;
 7 
 8 bool check[MAXN];
 9 int primes[MAXN];
10 int mu[MAXN];
11 
12 void moblus()
13 {
14     memset(check, false, sizeof(check));
15     mu[1] = 1;
16     int cnt = 0;
17     
18     for (int i = 2; i < MAXN; ++i) {
19         if (!check[i]) {
20             primes[cnt++] = i;
21             mu[i] = -1;
22         }
23         for (int j = 0; j < cnt; ++j) {
24             if (i * primes[j] > MAXN) break;
25             check[i * primes[j]] = true;
26             if (i % primes[j] == 0) {
27                 mu[i * primes[j]] = 0;
28                 break;
29             } else {
30                 mu[i * primes[j]] = -mu[i];
31             }
32         }
33     }
34 } 
35  
36  
37 int main()
38 {
39     moblus();
40     int nCase;
41     scanf("%d", &nCase);
42     while (nCase--) {
43         int n, m;
44         scanf("%d %d", &n, &m);
45         if (n < m) swap(n, m);
46         LL ans = 0;
47         for (int i = 1; i <= m; ++i) {
48             ans += (LL)mu[i] * (n / i) * (m / i);
49         }
50         printf("%lld
", ans);
51     }
52     return 0;
53 }