题目连接：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：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = ; bool check[MAXN];
int primes[MAXN];
int mu[MAXN]; void moblus()
{
memset(check, false, sizeof(check));
mu[] = ;
int cnt = ; for (int i = ; i < MAXN; ++i) {
if (!check[i]) {
primes[cnt++] = i;
mu[i] = -;
}
for (int j = ; j < cnt; ++j) {
if (i * primes[j] > MAXN) break;
check[i * primes[j]] = true;
if (i % primes[j] == ) {
mu[i * primes[j]] = ;
break;
} else {
mu[i * primes[j]] = -mu[i];
}
}
}
} int main()
{
moblus();
int nCase;
scanf("%d", &nCase);
while (nCase--) {
int n, m;
scanf("%d %d", &n, &m);
if (n < m) swap(n, m);
LL ans = ;
for (int i = ; i <= m; ++i) {
ans += (LL)mu[i] * (n / i) * (m / i);
}
printf("%lld\n", ans);
}
return ;
}