莫比乌斯反演学习笔记

证明：
我们可以把 $n$ 分解成 $\prod_{i = 1}^{k}p_i^{c_i}$ ，设 $n' = \prod_{i = 1}^{k}p_i$ ，那么有 $\sum_{d \mid n}\mu(n) = \sum_{d \mid n'}\mu(n) = \sum_{i = 1}^{k}\binom{k}{i} \cdot (-1)^i$ ，根据二项式定理， $\sum_{i = 1}^{k}\binom{k}{i} \cdot (-1)^i = [k = 0]$ ，所以只有在 $k = 0$ （即 $n = 1$ ）时原式为 $1$ ，其余时候都为 $0$ 。

这下子我们同时证明了 $(\mu * I)(n) = \epsilon(n)$ ，而 $\epsilon$ 是狄利克雷卷积的单位元，所以 $\mu$ 也可以定义为 $I$ 函数的逆元，也就是 $\mu = I^{-1}$ 。

~~现在你已经学会了莫比乌斯反演了~~

例题 Link to 例题

ZAP-Queries Link to

我们钦定 $a \le b$ ，先推式子：

\begin{aligned} ans & = \sum_{i = 1}^{a}\sum_{j = 1}^{b}[\gcd(i,j) = d] \\ & = \sum_{i = 1}^{a}\sum_{j = 1}^{b}[d \mid i][d \mid j][\gcd(\frac{i}{d},\frac{j}{d}) = 1] \\ & = \sum_{i = 1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{b}{d} \rfloor}[\gcd(i,j) = 1] \end{aligned}

（警觉起来）

我们发现出现了这么一个式子： $[\gcd(i,j) = 1]$ ，结合 $\sum_{d \mid n}\mu(d) = [n = 1]$ ，把 $\gcd(i,j) = 1$ 当做 $n$ ：

\begin{aligned} ans & = \sum_{i = 1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{b}{d} \rfloor}\sum_{g \mid \gcd(i,j)}\mu(g) \\ & = \sum_{g = 1}^{\lfloor \frac{a}{d} \rfloor}\mu(g)\sum_{i = 1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{b}{d} \rfloor}[g \mid i][g \mid j] \\ & = \sum_{g = 1}^{\lfloor \frac{a}{d} \rfloor}\mu(g)\sum_{i = 1}^{\lfloor \frac{a}{gd} \rfloor}\sum_{j = 1}^{\lfloor \frac{b}{gd} \rfloor}1 \\ & = \sum_{g = 1}^{n}\mu(g)\lfloor \frac{a}{gd} \rfloor \lfloor \frac{b}{gd} \rfloor \end{aligned}

化成这样我们就可以愉快的数论分块了，复杂度 $O(a + n\sqrt{a})$ 。其中 $n$ 来自预处理， $\sqrt{n}$ 来自数论分块的查询。

Crash 的数字表格 / JZPTAB Link to

钦定 $n \le m$ ，依然是推式子：

\begin{aligned} ans & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}\operatorname{lcm}(i,j) \\ & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}\frac{ij}{\gcd(i,j)} \\ & = \sum_{d = 1}^{n}\sum_{i = 1}^{n}\sum_{j = 1}^{m}\frac{ij}{d}[\gcd(i,j) = d] \\ & = \sum_{d = 1}^{n}\sum_{i = 1}^{n}\sum_{j = 1}^{m}\frac{ij}{d}[d \mid i][d \mid j][\gcd(\frac{i}{d},\frac{j}{d}) = 1] \\ & = \sum_{d = 1}^{n}\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}\frac{id \cdot jd}{d}[\gcd(i,j) = 1] \\ & = \sum_{d = 1}^{n}\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}ijd\sum_{g \mid \gcd(i,j)}\mu(g) \\ & = \sum_{d = 1}^{n}d\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}ij\sum_{g \mid \gcd(i,j)}\mu(g) \\ & = \sum_{d = 1}^{n}d\sum_{g = 1}^{\lfloor \frac{n}{d} \rfloor}\mu(g)\sum_{i = 1}^{\lfloor \frac{n}{gd} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{gd} \rfloor}ij \cdot g^2 \\ & = \sum_{d = 1}^{n}d\sum_{g = 1}^{\lfloor \frac{n}{d} \rfloor}g^2 \mu(g)\sum_{i = 1}^{\lfloor \frac{n}{gd} \rfloor}i\sum_{j = 1}^{\lfloor \frac{m}{gd} \rfloor}j \end{aligned}

我们发现 $\sum_{i = 1}^{\lfloor \frac{n}{gd} \rfloor}i$ 和 $\sum_{j = 1}^{\lfloor \frac{m}{gd} \rfloor}j$ 就是一个等差数列求和，可以 $O(1)$ 求，而 $\sum_{g = 1}^{\lfloor \frac{n}{d} \rfloor}g^2 \mu(g)$ 可以在线性筛的时候预处理，接下来就是愉快的数论分块时间了。

总结 Link to 总结

其实看上面两个题，你应该已经知道大概了流程了：先把枚举 $\gcd$ ，然后就会出现 $[\gcd(i,j) = 1]$ ，直接套上核心出装，然后来一个数论分块，这道题就做完了。

你可以通过下面的好题推荐来强化。

莫比乌斯反演学习笔记

约定 Link to 约定

引入 Link to 引入

前置知识 Link to 前置知识

一些基本函数 Link to 一些基本函数

狄利克雷卷积 Link to 狄利克雷卷积

定义 Link to 定义

性质 Link to 性质

正文 Link to 正文