莫比乌斯反演

莫比乌斯反演是数论中的重要内容，对于一些函数 $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$ 函数为积性函数，因此可以线性筛莫比乌斯函数（线性筛基本可以求所有的积性函数，尽管方法不尽相同）。

void getMu() {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!flg[i]) p[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
            flg[i * p[j]] = 1;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}

拓展

将 $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」简单的数学题