莫比乌斯函数
定义
定义函数 \mu (d)
还有一些常用的性质
1.最常用的: \forall n \in \N, \sum_{d|n} \mu(d) = [n=1].
2.\forall n \in \N, \sum_{d|n} \frac{\mu (d)}{d} = \frac{\varphi (n)}{d}
均不会证
Code
inline void getMu()
{
int siz = 10000000;
isPrime[1] = mu[1] = 1;
for (register int i = 2; i <= siz; ++ i) {
if (!isPrime[i]) {
prime[++ tot] = i, mu[i] = -1;
}
for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) {
isPrime[i * prime[j]] = 1;
if (i % prime[j]) mu[i * prime[j]] = -mu[i];
else {
mu[i * prime[j]] = 0;
break;
}
}
}
}
莫比乌斯反演
定理
设两个单元函数 F(x) , f(x) 分别为
F(x) = \sum_{d\mid n} f(d)
那么
f(x) = \sum_{d|n} \mu(d) F(\lfloor \frac{n}{d} \rfloor)
Summary
其实你根本不需要会这个反演,只需要知道上面那个最常用的性质就可以了
做几个题就会了
Comments | NOTHING