莫比乌斯反演

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

开始学习莫比乌斯反演前我们需要一些前置知识：积性函数、Dirichlet卷积、莫比乌斯函数

数论分块与整除相

引理 1

略证

引理 2

$_math_inline$|V|$math_inline_$ 表示集合 $_math_inline$V$math_inline_$ 的元素个数

略证

对于 $_math_inline$d\leq\lfloor\sqrt{n}\rfloor$math_inline_$ ， $_math_inline$\lfloor \frac{n}{d}\rfloor$math_inline_$ 有 $_math_inline$\lfloor\sqrt{n}\rfloor$math_inline_$ 种取值

对于 $_math_inline$d>\lfloor\sqrt{n}\rfloor$math_inline_$ ，有 $_math_inline$\lfloor \frac{n}{d}\rfloor\leq\lfloor\sqrt{n}\rfloor$math_inline_$ ，也只有 $_math_inline$\lfloor\sqrt{n}\rfloor$math_inline_$ 种取值

综上得证

数论分块

数论分块的过程大概如下：考虑含有 $_math_inline$\lfloor\frac{n}{i}\rfloor$math_inline_$ 的求和式子（ $_math_inline$n$math_inline_$ 为常数）

对于任意一个 $_math_inline$i(i\leq n)$math_inline_$ ，我们需要找到一个最大的 $_math_inline$j(i\leq j\leq n)$math_inline_$ ，使得 $_math_inline$\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor$math_inline_$

而 $_math_inline$j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$math_inline_$

略证

即 $_math_inline$j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$math_inline_$

利用上述结论，我们每次以 $_math_inline$[i,j]$math_inline_$ 为一块，分块求和即可

积性函数

定义

若 $_math_inline$\gcd(x,y)=1$math_inline_$ 且 $_math_inline$f(xy)=f(x)f(y)$math_inline_$ ，则 $_math_inline$f(n)$math_inline_$ 为积性函数。

性质

若 $_math_inline$f(x)$math_inline_$ 和 $_math_inline$g(x)$math_inline_$ 均为积性函数，则以下函数也为积性函数

例子

• 单位函数： $_math_inline$\epsilon(n)=[n=1]$math_inline_$
• 恒等函数： $_math_inline$\operatorname{id}_k(n)=n^k\operatorname{id}_{1}(n)$math_inline_$ 通常记做 $_math_inline$\operatorname{id}(n)$math_inline_$
• 常数函数： $_math_inline$1(n)=1$math_inline_$
• 除数函数： $_math_inline$\sigma_{k}(n)=\sum_{d\mid n}d^{k}\sigma_{0}(n)$math_inline_$ 通常简记做 $_math_inline$\operatorname{d}(n)$math_inline_$ 或 $_math_inline$\tau(n)$math_inline_$ ， $_math_inline$\sigma_{1}(n)$math_inline_$ 通常简记做 $_math_inline$\sigma(n)$math_inline_$
• 欧拉函数： $_math_inline$\varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]$math_inline_$
• 莫比乌斯函数： $_math_inline$\mu(n) = \begin{cases}1 & n=1 \\ 0 & \exists d:d^{2} \mid n \\ (-1)^{\omega(n)} & otherwise\end{cases}$math_inline_$ 其中 $_math_inline$\omega(n)$math_inline_$ 表示 $_math_inline$n$math_inline_$ 的本质不同质因子个数，是一个加性函数

Dirichlet卷积

定义

定义两个数论函数 $_math_inline$f,g$math_inline_$ 的Dirichlet卷积为

性质

Dirichlet卷积满足交换律和结合律

其中 $_math_inline$\varepsilon$math_inline_$ 为Dirichlet卷积的单位元（任何函数卷 $_math_inline$\epsilon$math_inline_$ 都为其本身）

例子

莫比乌斯函数

定义

$_math_inline$\mu$math_inline_$ 为莫比乌斯函数

性质

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

证明

其中 $_math_inline$\displaystyle\varepsilon(n)=\sum_{d\mid n}\mu(d)$math_inline_$ 即 $_math_inline$\varepsilon=\mu*1$math_inline_$

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

那么 $_math_inline$\displaystyle\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^k C_k^i\cdot(-1)^k$math_inline_$

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

补充结论

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

• **直接推导：**如果看懂了上一个结论，这个结论稍加思考便可以推出：如果 $_math_inline$\gcd(i,j)=1$math_inline_$ 的话，那么代表着我们按上个结论中枚举的那个 $_math_inline$n$math_inline_$ 是 $_math_inline$1$math_inline_$ ，也就是式子的值是 $_math_inline$1$math_inline_$ ，反之，有一个与 $_math_inline$[\gcd(i,j)=1]$math_inline_$ 相同的值：0
• **利用 $_math_inline$\varepsilon$math_inline_$ 函数：**根据上一结论， $_math_inline$[\gcd(i,j)=1]\Rightarrow \varepsilon(\gcd(i,j))$math_inline_$ ，将 $_math_inline$\varepsilon$math_inline_$ 展开即可。

线性筛

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

 1void getMu() {
 2    mu[1] = 1;
 3    for (int i = 2; i <= n; ++i) {
 4        if (!flg[i]) p[++tot] = i, mu[i] = -1;
 5        for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
 6            flg[i * p[j]] = 1;
 7            if (i % p[j] == 0) {
 8                mu[i * p[j]] = 0;
 9                break;
10            }
11            mu[i * p[j]] = -mu[i];
12        }
13    }
14}

拓展

将 $_math_inline$n$math_inline_$ 分解质因数： $_math_inline$\displaystyle n=\prod_{i=1}^k {p_i}^{c_i}$math_inline_$

首先，因为 $_math_inline$\varphi$math_inline_$ 是积性函数，故只要证明当 $_math_inline$n'=p^c$math_inline_$ 时 $_math_inline$\displaystyle\varphi*1=\sum_{d\mid n'}\varphi(\frac{n'}{d})=\text{ID}$math_inline_$ 成立即可。

因为 $_math_inline$p$math_inline_$ 是质数，于是 $_math_inline$d=p^0,p^1,p^2,\cdots,p^c$math_inline_$

易知如下过程

该式子两侧同时卷 $_math_inline$\mu$math_inline_$ 可得 $_math_inline$\displaystyle\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$math_inline_$

莫比乌斯反演

公式

设 $_math_inline$f(n),g(n)$math_inline_$ 为两个数论函数

如果有 $_math_inline$f(n)=\sum_{d\mid n}g(d)$math_inline_$

那么有 $_math_inline$g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})$math_inline_$

证明

**暴力计算：** $_math_inline$\sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n)$math_inline_$

用 $_math_inline$\displaystyle\sum_{d\mid n}g(d)$math_inline_$ 来替换 $_math_inline$f(\dfrac{n}{d})$math_inline_$ ，再变换求和顺序。最后一步转为的依据： $_math_inline$\displaystyle\sum_{d\mid n}\mu(d)=[n=1]$math_inline_$

因此在 $_math_inline$\dfrac{n}{k}=1$math_inline_$ 时第二个和式的值才为 $_math_inline$1$math_inline_$ 。此时 $_math_inline$n=k$math_inline_$ ，故原式等价于 $_math_inline$\displaystyle\sum_{k\mid n}[n=k]\cdot g(k)=g(n)$math_inline_$

运用卷积：

原问题为：已知 $_math_inline$f=g*1$math_inline_$ ，证明 $_math_inline$g=f*\mu$math_inline_$

易知如下转化： $_math_inline$f*\mu=g*1*\mu\Rightarrow f*\mu=g$math_inline_$ （其中 $_math_inline$1*\mu=\varepsilon$math_inline_$ ）

莫比乌斯反演拓展

对于数论函数 $_math_inline$f,g$math_inline_$ 和完全积性函数 $_math_inline$t$math_inline_$ 且 $_math_inline$t(1)=1$math_inline_$ ：

我们来证明一下：

解法二：

转化一下，可以将式子写成

容易知道

设 $_math_inline$sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij$math_inline_$ ，继续接着前面的往下推

这时我们只要对每个 $_math_inline$T$math_inline_$ 预处理出 $_math_inline$T\sum_{d\mid T}d\cdot\mu(d)$math_inline_$ 的值就行了，考虑如何快速求解

设 $_math_inline$f(n)=\sum_{d\mid n}d\cdot\mu(d)$math_inline_$

实际上 $_math_inline$f$math_inline_$ 可以用线性筛筛出，具体的是

其中 $_math_inline$p$math_inline_$ 表示 $_math_inline$n$math_inline_$ 的最小质因子

总时间复杂度 $_math_inline$O(n+\sqrt{n})$math_inline_$

例题

「HAOI 2011」Problem b

「SPOJ 5971」LCMSUM

「BZOJ 2154」Crash 的数字表格

「SDOI2015」约数个数和

「luogu 3768」简单的数学题