莫比乌斯函数

定义

定义函数 $\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} $$

还有一些常用的性质

1. 最常用的: $\forall n \in N, \sum_{d|n} = [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

其实你根本不需要会这个反演,只需要知道上面那个最常用的性质就可以了

基本的东西做几个题就会了