莫比乌斯反演

引入

莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$，如果很难直接求出它的值，而容易求出其倍数和或约数和 $g(n)$，那么可以通过莫比乌斯反演简化运算，求得 $f(n)$ 的值。

定义

$\mu$ 为莫比乌斯函数，定义为

$$
\mu(n)=
\begin{cases}
1&n=1\
0&n\text{ 含有平方因子}\
(-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\
\end{cases}
$$

详细解释一下：

令 $n=\prod_{i=1}^kp_i^{c_i}$，其中 $p_i$ 为质因子，$c_i\ge 1$。上述定义表示：

1. $n=1$ 时，$\mu(n)=1$；
2. 对于 $n\not= 1$ 时：
   1. 当存在 $i\in [1,k]$，使得 $c_i > 1$ 时，$\mu(n)=0$，也就是说只要某个质因子出现的次数超过一次，$\mu(n)$ 就等于 $0$；
   2. 当任意 $i\in[1,k]$，都有 $c_i=1$ 时，$\mu(n)=(-1)^k$，也就是说每个质因子都仅仅只出现过一次时，即 $n=\prod_{i=1}^kp_i$，${p_i}_{i=1}^k$ 中个元素唯一时，$\mu(n)$ 等于 $-1$ 的 $k$ 次幂，此处 $k$ 指的便是仅仅只出现过一次的质因子的总个数。

性质

莫比乌斯函数不仅是积性函数，还有如下性质：

$$
\sum_{d\mid n}\mu(d)=
\begin{cases}
1&n=1\
0&n\neq 1\
\end{cases}
$$

即 $\sum_{d\mid n}\mu(d)=\varepsilon(n)$，$\mu * 1 =\varepsilon$

重要的转换方式:
如果有$\color{red}{f(n)=\sum_{d\mid n}g(d)}$,则有$\color{blue}{g(n)=\sum_{d|n}f(d)\mu(\frac{n}{d})}$.
如果有$\color{red}{f(n)=\sum_{n\mid d}g(d)}$,则有$\color{blue}{g(n)=\sum_{n|d}f(d)\mu(\frac{d}{n})}$.

证明

设 $\displaystyle n=\prod_{i=1}^k{p_i}^{c_i},n’=\prod_{i=1}^k p_i$

那么 $\displaystyle\sum_{d\mid n}\mu(d)=\sum_{d\mid n’}\mu(d)=\sum_{i=0}^k \dbinom{k}{i}\cdot(-1)^i=(1+(-1))^k$

根据二项式定理，易知该式子的值在 $k=0$ 即 $n=1$ 时值为 $1$ 否则为 $0$，这也同时证明了 $\displaystyle\sum_{d\mid n}\mu(d)=[n=1]=\varepsilon(n)$ 以及 $\mu\ast 1=\varepsilon$

所以在狄利克雷卷积中，莫比乌斯函数是常数函数 $1$ 的逆元。

补充结论

反演结论：$\displaystyle [\gcd(i,j)=1]=\sum_{d\mid\gcd(i,j)}\mu(d)$

直接推导：如果看懂了上一个结论，这个结论稍加思考便可以推出：如果 $\gcd(i,j)=1$ 的话，那么代表着我们按上个结论中枚举的那个 $n$ 是 $1$，也就是式子的值是 $1$，反之，有一个与 $[\gcd(i,j)=1]$ 相同的值：$0$

利用 $\varepsilon$ 函数：根据上一结论，$[\gcd(i,j)=1]=\varepsilon(\gcd(i,j))$，将 $\varepsilon$ 展开即可。

线性筛

由于 $\mu$ 函数为积性函数，因此可以线性筛莫比乌斯函数（线性筛基本可以求所有的积性函数，尽管方法不尽相同）。

int pri[50005],mu[50005],tot;
bool vis[50005];
void get_mu(int n){
    mu[1]=1;//注意初始化
    for(int i = 2;i<=n;i++){
        if(!vis[i]){
            pri[++tot]=i;
            mu[i]=-1;//是质数
        }
        for(int j = 1;i*pri[j]<=n&&j<=tot;j++){
            int m=i*pri[j];
            vis[m]=1;
            if(i%pri[j]==0){
                mu[m]=0;//有平方因子
                break;
            }
            mu[m]=-mu[i];
        }
    }
}