题目连接：

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

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

code：

1 #include 
     
       2 #include 
      
        3 #include 
       
         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\n", ans);51     }52     return 0;53 }