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:

 #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 ;
}
上一篇:int与CString互相转化


下一篇:ElasticSearch学习问题记录——Invalid shift value in prefixCoded bytes (is encoded value really an INT?)