浅谈莫比乌斯反演

那些各种各样的性质与定理,大多是前人几年甚至几十年才得出来的,哪里是你几天就能理解并证明的。

简介

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

--OI Wiki

莫比乌斯函数

定义

$$\mu(d)=\begin{cases}1&d=1\\(-1)^k&d=\prod_{i=1}^kp_i\text{且}p_i\text{为互不相同的质数}\\0&d\text{含有平方因子}\end{cases}$$

令 $n=\prod_{i=1}^k p_i^{c_i}$，其中 $p_i$ 为质因子，$c_i\ge 1$。

1. 当 $n=1$ 时，$\mu(n)=1$。
2. 当 $n\not = 1$ 时：

• 若 $\exists i\in[1,k],c_i>1$，那么 $\mu(n)=1$。
• 若 $\forall i \in [1,k],c_i=1$，那么 $\mu(n)=(-1)^k$。

性质

莫比乌斯函数是积性函数，并且有以下性质：

1. $$\sum\limits_{dn}\mu(d)=\begin{cases}1 & n=1\\0 & n\not = 1\end{cases}$$
2. $$\sum\limits_{dn}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}$$

求法

由于莫比乌斯函数是典型的积性函数，所以也可以用欧拉筛筛出来。

I void GM(){
    RI i,j;for(mu[1]=1,i=2;i<N;i++) for(!v[i]&&(mu[p[++tot]=i]=-1,0),j=1;j<=tot&&i*p[j]<N;j++)
    if(v[i*p[j]]=1,i%p[j]) mu[i*p[j]]=-mu[i];else break ;
    for(i=1;i<N;i++) mu[i]+=mu[i-1];
}

莫比乌斯反演

令 $F(n)$ 与 $f(n)$ 为定义在非负整数域上的两个函数，且他们之间满足 $$F(n)=\sum\limits_{dn}f(d)$$。

那么我们有 $$f(n)=\sum\limits_{dn}\mu(d)F(\lfloor \frac{n}{d}\rfloor)$$

这就是莫比乌斯反演定理，它还有另外一种形式：

如果 $$F(n)=\sum\limits_{nd}f(d)$$

那么我们有 $$f(n)=\sum\limits_{nd}\mu(\frac{d}{n})F(d)$$

例题

基础题

• P2522 [HAOI2011]Problem b
• P3455 [POI2007]ZAP-Queries
• P2257 YY的GCD

提高题

咕了