莫比乌斯反演

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

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

数论分块与整除相

引理 1

略证

引理 2

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

略证

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

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

综上得证

数论分块

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

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

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

略证

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

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

积性函数

定义

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

性质

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

例子

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

Dirichlet卷积

定义

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

性质

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

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

例子

莫比乌斯函数

定义

$\mu$ 为莫比乌斯函数

性质

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

证明

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

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

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

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

补充结论

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

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

线性筛

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

c++ ▽
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];
        }
    }
}

拓展

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

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

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

易知如下过程

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

莫比乌斯反演

公式

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

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

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

证明

**暴力计算：** $\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)$

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

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

运用卷积：

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

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

莫比乌斯反演拓展

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

我们来证明一下：

解法二：

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

容易知道

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

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

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

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

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

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

例题

「HAOI 2011」Problem b

「SPOJ 5971」LCMSUM

「BZOJ 2154」Crash 的数字表格

「SDOI2015」约数个数和

「luogu 3768」简单的数学题