莫比乌斯函数
定义
定义函数 $\mu (d)$
$$ \begin{equation} \mu(d)= \left\{ \begin{array}{lr} 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d=1\\ (-1)^k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d= \prod_{i=1}^{k} p_i \ \& \ \forall i,j \in [1,k], p_i \not= p_j \\ 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall c_i \geq 2 \end{array} \right. \end{equation} $$
还有一些常用的性质
- 最常用的: $\forall n \in N, \sum_{d|n} = [n=1]$
- $\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
其实你根本不需要会这个反演,只需要知道上面那个最常用的性质就可以了
基本的东西做几个题就会了