「OI」莫比乌斯反演

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

开始学习莫比乌斯反演前,我们需要一些前置知识:积性函数 、$ \texttt {Dirichlet} $ 卷积、莫比乌斯函数。

前置知识

简单数论函数

数论函数指的是定义域、值域都是正整数的有关数论的函数,下面介绍几个常见的数论函数。

单位函数

$$ \epsilon ( x ) = [ x = 1] $$

上面的式子里面的 $ [ n ] $ 是特征函数,如果里面的表达式成立,则值为 $ 1 $,否则为 $ 0 $。

恒等函数

$$ \operatorname {id} _ k ( x ) = x ^ k $$

并且 $ \operatorname {id} _ 1 ( x ) $ 通常简记为 $ \operatorname {id} ( x ) $。

常数函数

$$ \operatorname {1} ( x ) = 1 $$

这是一个常函数,$ \forall x \in \mathbb {Z} , \operatorname {1} ( x ) = 1 $。

除数函数

$$ \sigma _ k ( x ) = \sum _ { d \mid x } d ^ k \sigma _ 0 ( x ) $$

并且 $ \sigma _ 1 ( x ) $通常简记为 $ \sigma ( x ) $。

不难发现 $ \sigma _ 0 ( x ) $ 可以表示 $ x $ 的约数个数,$ \sigma _ 1 ( x ) $ 表示 $ x $ 的约数和,更加一般地,我们有:

$$ x = \prod p _ i ^ { c _ i } $$

$$ \sigma _ k ( x ) = \sum _ { p _ i } \sum ^ { c _ i } _ { i = 0 } p _ i ^ { k \times i } $$

欧拉函数

$$ \varphi ( x ) = \sum _ { i = 1 } ^ n [ \gcd ( i , n ) = 1 ] $$

关于欧拉函数,更多的可以看我的博客「OI」欧拉函数 φ(n)

莫比乌斯函数

$$
\mu ( x ) = \begin {cases}
1 & n = 1 \\
0 & \exists d : d ^ 2 \mid n \\
( – 1 ) ^ { \omega ( x ) } & \text {otherwise}
\end {cases}
$$

其中 $ \omega ( x ) $ 表示 $ x $ 的本质不同质因子个数。

积性函数

定义

如果有一个数论函数 $ f ( x ) $ 满足:

$$ \gcd ( a , b ) = 1 \Rightarrow f ( a b ) = f ( a ) f ( b ) $$

那么就说 $ f ( x ) $ 是一个积性函数。

运用

首先不难发现,上面列出的函数都是积性函数,我们可以通过上面给出的计算式带入证明。

此外,我们还可以发现,积性函数都是可以在 $ \Theta ( n ) $ 内的时间用线性筛求出。

Dirichlet 卷积

定义

对于两个数论函数 $ f , g $,它们的 $ \texttt {Dirichlet} $ 卷积为:

$$ ( f \ast g ) ( n ) = \sum _ { d \mid n } f ( d ) g ( \frac { n } { d } ) $$

性质

$ \texttt {Dirichlet} $ 卷积满足交换律和结合律。

其中 单位函数 $ \epsilon $ 为 $ \texttt {Dirichlet} $ 卷积的单位元(任何函数卷 $ \epsilon $ 都为其本身)。

重要结论

这里有两个重要结论。

  1. $$ \mu = 1 ^ { – 1 } $$

证明 $ \mu = 1 ^ { – 1 } $,即证 $ \mu \ast 1 = \epsilon $,下面我们主要来证明这个命题。

考虑 $ n = 1 $,$ \mu ( 1 ) \times 1 ( 1 ) = [ 1 = 1 ] $,显然成立。

考虑 $ n \ne 1$,我们需要证明 $\sum _ {d\mid n}\mu(d)=0$。

因为 $\mu(d)$ 仅在 $d$ 没有平方因子时对答案有贡献,所以我们只要考虑 $n$ 以内的质数的组合,即 $\sum _ {d\mid n}\mu(d)=\sum _ {d\mid n’}\mu(d)$,其中 $n’$ 为 $n$ 的所有质因子的乘积。

$$\sum _ {d\mid n’}\mu(d)=\sum _ {r=0}^{\omega(n’)}(-1)^r=(1-1)^{\omega(n’)}=0$$

得证 $\mu\ast 1=\epsilon$,继而 $\mu=1^{-1}$。

  1. $$\varphi\ast 1=\operatorname{id}$$

证明 $\varphi\ast 1=\operatorname{id}$ 等价于证明 $\sum _ {d\mid n}\varphi(d)=n$,下面我们来证明这个命题。

考虑一个集合 $\frac{1}{n},\frac{2}{n},\cdots,\frac{n}{n}$,这个集合元素个数为 $n$。

考虑枚举 $n$ 与 $i\in[1,n]$ 的最大公因数,那么这个最大公因数必定是 $n$ 的因数。

考虑到分数的化简,发现对于化简后以 $a$ 为分母的数有 $\varphi(a)$ 个,并且没有哪个数化简后会有两个分母。

所以我们有:

$$\sum _ {d\mid n}\varphi(d)=n$$

莫比乌斯反演

定理内容

如果有两个数论函数 $f(n),g(n)$ 满足:

$$f(n)=\sum _ {d\mid n}g(d)$$

那么我们有:

$$g(n)=\sum _ {d\mid n}\mu(d)f(\frac{n}{d})$$

证明

欲证
$$g(n)=\sum _ {d\mid}\mu(d)f(\frac{n}{d})$$

即证
$$(f\ast\mu)(n)=g(n)$$


$$(\mu\ast 1)(n)=\epsilon(n)$$

所以两边同时卷上 $1(n)$。
$$(f\ast\mu\ast 1)(n)=(g\ast 1)(n)$$

此时化简可知我们只要证明
$$(f\ast\epsilon)(n)=(g\ast 1)(n)$$


$$f(n)=(g\ast 1)(n)$$

这是给出的条件,所以原命题成立。

题外话

莫比乌斯反演这个定理的内容其实很简单,但是应用比较复杂,题目的式子也很难推,下面我们一起看看几个简单的式子。

莫比乌斯反演的应用(推式子)

莫比乌斯反演常常与数论分块、前缀和、杜教筛之类的东西混在一起用。

下面有一些例题中的式子的推导过程。

「POI2007」ZAP-Queries

具体的内容可以看我的博客。

题面

给定 $n(n\leq 5\times 10^4)$ 组 $a,b,d(a,b,d\leq 5\times 10^4)$,对于每组数据,求

$$\sum^a _ {i=1}\sum^b _ {j=1}[\gcd(i,j)=d]$$

推导

不妨设 $g(d)$ 表示 $a,b$ 以内的 $\gcd$ 为 $d$ 的数对个数,则
$$g(d)=\sum^a _ {i=1}\sum^b _ {j=1}[\gcd(i,j)=d]$$

另外,不妨设 $f(n)$ 表示 $a,b$ 以内的 $\gcd$ 为 $n$ 和 $n$ 的倍数的数对个数,则
$$f(n)=\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor$$

根据 $f(n)$ 和 $g(d)$ 的定义,我们不难发现
$$f(n)=\sum _ {n\mid k}g(k)$$

用莫比乌斯反演变换一下。
$$g(n)=\sum _ {n\mid k}\mu(\frac{k}{n})f(k)$$

把 $f(n)$ 的式子带入,得出答案
$$\texttt{ans}=g(d)=\sum _ {d\mid k}\mu(\frac{k}{d})\lfloor\frac{a}{k}\rfloor\lfloor\frac{b}{k}\rfloor$$

继而
$$\texttt{ans}=\sum^{\min\{a,b\}} _ {t=1}\mu(t)\lfloor\frac{a}{td}\rfloor\lfloor\frac{b}{td}\rfloor$$

「SDOI2015」约数个数和

具体的题目可以看我的博客。

题面

$T(T\leq 5\times 10^4)$ 组数据,每组数据给定 $n,m(n,m\leq 5\times 10^4)$,求
$$\sum^n _ {i=1}\sum^m _ {j=1}\sigma _ 0(ij)$$

推导

显然有
$$\sigma _ 0(ij)=\sum _ {x\mid i}\sum _ {y\mid j}[\gcd(x,y)=1]$$

带入原式可得所求为
$$\sum^n _ {i=1}\sum^m _ {j=1}\sum _ {x\mid i}\sum _ {y\mid j}[\gcd(x,y)=1]$$

化简
$$\sum^n _ {i=1}\sum^m _ {j=1}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\gcd(i,j)=1]$$

我们不妨设
$$
f(x)=\sum^n _ {i=1}\sum^m _ {j=1}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\gcd(i,j)=x]\\
g(x)=\sum _ {x\mid d}f(d)
$$

所以可知
$$g(x)=\sum^n _ {i=1}\sum^m _ {j=1}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[x\mid\gcd(i,j)]$$

提出 $x$
$$g(x)=\sum^{\lfloor\frac{n}{x}\rfloor} _ {i=1}\sum^{\lfloor\frac{m}{x}\rfloor} _ {j=1}\lfloor\frac{n}{ix}\rfloor\lfloor\frac{m}{jx}\rfloor$$


$$g(x)=\sum _ {x\mid d}f(d)$$

莫比乌斯反演得
$$f(x)=\sum _ {n\mid d}\mu(\frac{d}{n})g(d)$$


$$\texttt{ans}=f(1)=\sum _ {1\mid d}\mu(d)g(d)=\sum^n _ {i=1}\mu(i)g(i)$$

参考资料