浅谈莫比乌斯反演

浅谈莫比乌斯反演

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

简介

莫比乌斯反演是数论中的重要内容。对于一些函数 $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}$$

求法

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

1
2
3
4
5
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

提高题

咕了