数论分块与 Möbius 反演学习笔记
xk2013
·
2026-07-24 14:44:12
·
算法·理论
前言
笔者学习 Möbius 反演时，由于网络上的各种资料有时候光给出性质，而不给出证明，让笔者难以理解，原因是我太菜了，为了造福后人，写下了这篇文章，因此也融入了自己对 Möbius 反演的一些体会和方法论，希望能够帮助大家更好地理解这一知识点。
本文中所有的数默认都为正整数 ，共 24870 字，有点长，可以分块食用。
数论分块的概念与性质
数论分块是分块（即答）。
数论分块虽然并不是传统数据结构中所说的“分块”，但是也沿用了分块的思想。
数论分块一般用来算这种求和：
\sum\limits_{i=1}^nf(i)g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)
其中 f(i) 的前缀和通常是可以快速计算或者是可以预处理的。
那么数论分块的“分块”到底在哪里呢？藏在右边这个下取整这里。容易发现下取整会让其变成一块一块的。
性质一 ：\left\lfloor\dfrac{n}{i}\right\rfloor 只有不超过 2\sqrt n 种取值，即只有 \Omicron(\sqrt n) 种取值，进而只有 \Omicron(\sqrt n) 个“块”。
:::success[证明]
考虑分类讨论。
当 i \le \sqrt n 时，因为 i 只有 \sqrt n 种取值，因此 \left\lfloor\dfrac{n}{i}\right\rfloor 也只有不超过 \sqrt n 种取值；
当 i > \sqrt n 时，显然有 1 \le \left\lfloor\dfrac{n}{i}\right\rfloor \le \sqrt n ，即此时 \left\lfloor\dfrac{n}{i}\right\rfloor 也只有不超过 \sqrt n 种取值。
综上所述，\left\lfloor\dfrac{n}{i}\right\rfloor 只有不超过 2\sqrt n 种取值，证毕。
:::
性质二 ：若存在取值 d ，则使得 \left\lfloor\dfrac{n}{i}\right\rfloor = d 的 i 取值范围为 \left\lfloor\dfrac{n}{d+1}\right\rfloor + 1 \le i \le \left\lfloor\dfrac{n}{d}\right\rfloor 。
:::success[证明]
倒过来可得 $\dfrac{1}{d + 1} < \dfrac{i}{n} \le \dfrac{1}{d}$，同时乘 $n$ 得 $\dfrac{n}{d + 1} < i \le \dfrac{n}{d}$。
由于 $i$ 是正整数，因此有 $\left\lfloor\dfrac{n}{d+1}\right\rfloor < i \le \left\lfloor\dfrac{n}{d}\right\rfloor$，即 $\left\lfloor\dfrac{n}{d+1}\right\rfloor + 1 \le i \le \left\lfloor\dfrac{n}{d}\right\rfloor$。
证毕。
:::
**性质二**让我们可以快速确定左右端点 $l, r$（$l$ 为上一块右端点加 $1$，$r = \left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor$）。确定了块端点后，这一块对答案的贡献即为：
$$\sum\limits_{i=l}^rf(i)g\left(\left\lfloor\dfrac{n}{l}\right\rfloor\right) = g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\sum\limits_{i=l}^rf(i)$$
由于后面已经预处理好了，所以这个式子可以 $\Omicron(1)$ 计算，而总共只有 $\Omicron(\sqrt n)$ 块，因此计算的时间复杂度即为 $\Omicron(\sqrt n)$。
## Möbius 函数及其性质
大家都知道 Möbius 函数 $\mu(n)$：
记 $\mathbb P$ 为质数集合，设 $n$ 的质因数分解形式为 $\displaystyle n = \prod\limits_{p_i \in \mathbb P} p_i^{k_i}$，$c$ 为非零的 $k_i$ 个数。则：
$$\mu(n) = \begin{cases}
0, &\exists k_i \ge 2\\
(-1)^c, &\text{otherwise.}
\end{cases}$$
$\mu(n)$ 显然是积性函数。$\mu(n)$ 有如下性质：
**性质一**：$\displaystyle\sum\limits_{d~\vert~ n} \mu(d) = [n = 1] = \varepsilon(n)$。
:::success[证明]
当 $n = 1$ 时，性质显然成立。下面我们讨论 $n > 1$ 的情况。
记 $\displaystyle F(n) = \sum\limits_{d~\vert~ n} \mu(d) = (\mu \ast 1)(n)$。由 Dirichlet 卷积的性质，两个积性函数的 Dirichlet 卷积还是一个积性函数，因此 $F(n)$ 是积性函数。
设 $n$ 的质因数分解形式为 $\displaystyle n = \prod\limits_{p_i \in \mathbb P} p_i^{k_i}$。则我们有 $\displaystyle F(n) = \prod\limits_{p_i\in \mathbb P} F(p_i^{k_i})$。
考虑：
$$
\begin{aligned}
F(p_i^{k_i})
&= \sum\limits_{d~\vert~ p_i^{k_i}} \mu(d)\\
&= \sum\limits_{j = 0}^{k_i} \mu(p_i^j)\\
&= \mu(1) + \mu(p) + \mu(p^2) + \cdots\\
&= \mu(1) + \mu(p)\\
&= 1 + (-1)\\
&= 0
\end{aligned}
$$
因此 $F(n) = 0$（$n > 1$）。由 Dirichlet 卷积单位元 $\varepsilon(n)$ 的定义，有 $\varepsilon(n) = [n = 1] = F(n)$，证毕。
:::
**性质二**：$\displaystyle\sum\limits_{d~\vert~n}\dfrac{\mu(d)}{d} = \dfrac{\varphi(n)}{n}$。
:::success[证明]
由 Dirichlet 卷积的**结论**，$\varphi = \mu \ast \operatorname{id}$，展开得到：
$$\varphi(n) = \sum\limits_{d ~\vert~ n} \mu(d)\operatorname{id}(\dfrac{n}{d}) = n\sum\limits_{d ~\vert~ n} \dfrac{\mu(d)}{d}$$
左右各除以一个 $n$ 即得到原式，证毕。
:::
有了这些性质，我们就可以来探究 Möbius 反演了，顺便还能知道 Möbius 函数 $\mu(n)$ 是怎么来的。
## Möbius 反演及其应用
首先假装我们有一个数论函数 $f(n)$，且 $f \ast 1 = F$（即 $\displaystyle F(n) = \sum\limits_{d~\vert~n}f(d)$），那么我们有：
$$f(n) = \sum\limits_{d~\vert~n}\mu(d)F(\dfrac{n}{d})$$
这种逆变换被我们称为 **Möbius 反演**。
:::success[证明]
我们选择直接暴力展开。
$$
\begin{aligned}
\sum\limits_{d~\vert~n}\mu(d)F(\dfrac{n}{d})
&= \sum\limits_{d~\vert~n}\mu(d)\sum\limits_{k~\vert~\dfrac{n}{d}}f(k)\\
&= \sum\limits_{dk~\vert~n}\mu(d)f(k)\\
&= \sum\limits_{dk~\vert~n}\mu(k)f(d)\\
&= \sum\limits_{d~\vert~n}f(d)\sum\limits_{k~\vert~\dfrac{n}{d}}\mu(k)\\
&= \sum\limits_{d~\vert~n}f(d)[\dfrac{n}{d}=1]\\
&= \sum\limits_{d~\vert~n}f(d)[d=n]\\
&= f(n)
\end{aligned}
$$
第一步是按照定义展开，第三步交换了求和顺序，是数论证明中常用的手法。第五步用了 Möbius 函数的**性质一**。
证毕。
:::
其实这才是 Möbius 函数 $\mu(n)$ 原本的定义。
那么 Möbius 反演到底有什么用处呢？我们来做点例题。
先来一道开胃小菜。
----------------------
### [例题 1：BZOJ #3561. DZY Loves Math VI](https://darkbzoj.cc/problem/3561)
:::info[如果你打不开题：简要题意]{open}
给定 $n, m$，求：
$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \operatorname{lcm}(i, j)^{\gcd(i, j)}$$
其中 $\operatorname{lcm}(i, j)$ 表示 $i, j$ 的最小公倍数，$\gcd(i, j)$ 表示 $i, j$ 的最大公因数。
数据范围：$1 \le n, m \le 5 \times 10^5$。
:::
在推式子前，我们不妨假定 $n \le m$，如果不满足交换即可，不影响答案。
然后开始我们的推式子环节：
$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m \operatorname{lcm}(i, j)^{\gcd(i, j)}
&=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left(\dfrac{ij}{d}\right)^d[\gcd(i, j) = d]\\
&= \sum\limits_{d=1}^n\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor} (ijd)^d[\gcd(i, j) = 1]\\
&= \sum\limits_{d=1}^nd^d\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor} (ij)^d[\gcd(i, j) = 1]\\
&= \sum\limits_{d=1}^nd^d\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor} (ij)^d\sum\limits_{k~\vert~\gcd(i, j)}\mu(k)\\
&= \sum\limits_{d=1}^nd^d\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor} (ij)^d\sum\limits_{k~\vert~i, k~\vert~j}\mu(k)\\
&= \sum\limits_{d=1}^nd^d\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor} \sum\limits_{k~\vert~i, k~\vert~j}(ij)^d\mu(k)\\
&= \sum\limits_{d=1}^nd^d\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\mu(k)\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{dk}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{dk}\right\rfloor} (ijk^2)^d\\
&= \sum\limits_{d=1}^nd^d\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}k^{2d}\mu(k)\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{dk}\right\rfloor}i^d\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{dk}\right\rfloor}j^d\\
&= \sum\limits_{d=1}^nd^d\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}k^{2d}\mu(k)S_d\left(\left\lfloor\dfrac{n}{dk}\right\rfloor\right)S_d\left(\left\lfloor\dfrac{m}{dk}\right\rfloor\right)
\end{aligned}
$$
其中 $\displaystyle S_d(n) = \sum\limits_{i=1}^n i^d$ 被称为**自然数幂和**，使用 $\Omicron(n \log n)$ 朴素的快速幂直接算。
来对上面的推式子做一些解释：
1. 第一步枚举了最大公因数，这是数论问题常用的处理方法；
2. 第二步我们其实做了个换元，将 $i' = id$，$j' = jd$ 然后提取出来；
3. 第三步交换求和顺序，没什么好说的；
4. 第四步利用了 Möbius 函数的**性质一**，将互质的条件巧妙地消掉了。这也是 Möbius 函数**性质一**如此重要的原因；
5. 第七步又是一个换元，相信大家能够看懂；
对于其他式子中的项，$\mu(k)$ 可以线性筛 $\Omicron(n)$ 预处理，其他带 $d$ 次方的可以快速幂或者动态维护。让我们来算下复杂度：
:::warning[复杂度分析，可以跳过]
$$
\begin{aligned}
T(n)
&= \sum\limits_{d=1}^n\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\Omicron\left(\left\lfloor\dfrac{n}{dk}\right\rfloor \log \left\lfloor\dfrac{n}{dk}\right\rfloor\right)\\
&\le \Omicron(\log n) \sum\limits_{d=1}^n\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\Omicron\left(\left\lfloor\dfrac{n}{dk}\right\rfloor\right)\\
&= \Omicron(n \log n)\sum\limits_{d=1}^n\Omicron\left(\dfrac{1}{d}\right)\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\Omicron\left(\dfrac{1}{k}\right)\\
&= \Omicron(n \log n)\sum\limits_{d=1}^n\Omicron\left(\dfrac{1}{d} \log \dfrac{n}{d}\right)\\
&= \Omicron(n \log n)~\Omicron(\log^2 n)\\
&= \Omicron(n \log^3 n)
\end{aligned}
$$
:::
$\Omicron(n \log^3 n)$！天哪竟然是惊人的三只 $\log$！~~这肯定过不去~~，我们考虑优化。发现我们可以在枚举 $k$ 之前预处理当前的 $S_d(n)$，而不是每次枚举一个 $k$ 又算一遍，可以去掉一个 $\log$ 变成 $\Omicron(n \log^2 n)$，[可以跑过去了](https://darkbzoj.cc/submission/284103)。
当然我们还可以优化。我们只需要当每次 $d$ 增加的时候，递推 $i^d$ 的值（$i^d = i^{d - 1} \times i$），这样只会增加 $\displaystyle\sum\limits_{d=1}^n \Omicron\left(\left\lfloor\dfrac{n}{d}\right\rfloor\right) = \Omicron(n \log n)$ 的代价，而去掉了快速幂的一只 $\log$，可以做到 $\Omicron(n \log n)$ 的时间复杂度，~~反正我是不会写的~~。
这个题很适合作为 Möbius 反演的第一道入门题，~~能让你感受到推式子的魅力~~。
----------------------
### [例题 2：洛谷 P2522 [HAOI2011] Problem b](/problem/P2522)
有了前面的经验，先请读者自行思考一下再继续往下读。
----------------------
我们发现求和有上下界，不是很好处理。那就干脆直接把它容斥掉！
记 $\displaystyle f(n, m, k) = \sum\limits_{i = 1}^n\sum\limits_{j=1}^m[\gcd(i, j) = k]$。于是本题的答案即为 $f(b, d, k) - f(b, c - 1, k) - f(a - 1, d, k) + f(a - 1, c - 1, k)$。我们只需要考虑一下 $\displaystyle f(n, m, k) = \sum\limits_{i = 1}^n\sum\limits_{j=1}^m[\gcd(i, j) = k]$ 怎么算就行了。
不妨设 $n \le m$，显然交换 $n, m$ 不影响 $f(n, m, k)$。按照前面的套路，我们进行推式子：
$$
\begin{aligned}
f(n, m, k)
&= \sum\limits_{i = 1}^n\sum\limits_{j=1}^m[\gcd(i, j) = k]\\
&= \sum\limits_{i=1}^{\left\lfloor\dfrac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{k}\right\rfloor}[\gcd(i, j) = 1]\\
&= \sum\limits_{i=1}^{\left\lfloor\dfrac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{k}\right\rfloor}\sum\limits_{d~\vert~\gcd(i, j)} \mu(d)\\
&= \sum\limits_{d=1}^{\left\lfloor\dfrac{n}{k}\right\rfloor}\mu(d)\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{dk}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{dk}\right\rfloor}1\\
&= \sum\limits_{d=1}^{\left\lfloor\dfrac{n}{k}\right\rfloor}\mu(d)\left\lfloor\dfrac{n}{dk}\right\rfloor\left\lfloor\dfrac{m}{dk}\right\rfloor
\end{aligned}
$$
推到这里已经可以做到 $\Omicron(n)$ 了，但是可恶的出题人开了多组数据，$\Omicron(Tn)$ 很可能过不去。我们注意到 $\left\lfloor\dfrac{n}{dk}\right\rfloor = \left\lfloor\dfrac{\left\lfloor\dfrac{n}{d}\right\rfloor}{k}\right\rfloor$，$m$ 也是同理，而分子上的都是常数。
看到这个你想到了什么？对，数论分块！利用数论分块我们就可以轻松做到 $\Omicron(T\sqrt{n})$ 的优秀复杂度了。[复杂度很优秀，但是有容斥的 $4$ 倍常数](/record/288333941)。
----------------------
### [例题 3：洛谷 P2257 YY的GCD](/problem/P2257)
相信经过前两题的历练，你应该已经掌握了一些推式子的技巧了吧！
~~推式子是不是很好玩，很爽？~~
这道题跟上一道题有相似之处，先自己推推看式子吧。
----------------------
我们依然可以套路化地枚举 $\gcd$，但是这次的枚举范围变成了质数集合 $\mathbb P$。
不妨设 $n \le m$，我们来推柿子：
$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i, j) \in \mathbb P]
&= \sum\limits_{p\in\mathbb P\cap[1, n]}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i, j) = p]\\
&= \sum\limits_{p\in\mathbb P\cap[1, n]}\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{p}\right\rfloor}[\gcd(i, j) = 1]\\
&= \sum\limits_{p\in\mathbb P\cap[1, n]}\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{p}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{p}\right\rfloor}\sum\limits_{k ~\vert~ \gcd(i, j)}\mu(k)\\
&= \sum\limits_{p\in\mathbb P\cap[1, n]}\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{p}\right\rfloor}\mu(k)\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{pk}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{pk}\right\rfloor} 1\\
&= \sum\limits_{p\in\mathbb P\cap[1, n]}\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{p}\right\rfloor}\left\lfloor\dfrac{n}{pk}\right\rfloor\left\lfloor\dfrac{m}{pk}\right\rfloor\mu(k)\\
\end{aligned}
$$
看起来这个式子已经非常的友好了，算一下暴力算的复杂度 $\Omicron\left(\displaystyle\sum\limits_{p\in\mathbb P\cap [1, n]}\left\lfloor\dfrac{n}{p}\right\rfloor\right) = \Omicron(n \log \log n)$（这个式子其实跟埃氏筛的复杂度一模一样）。
但是！又有多组数据，而且 $T = 10^4$，这显然跑不过去，哎呀这个题怎么这么坏。套路地，我们依旧考虑数论分块。但是这里还有一维枚举质数的去不掉，没法直接数论分块……所以还得继续推！
$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i, j) \in \mathbb P]
&= \sum\limits_{p\in\mathbb P\cap[1, n]}\sum\limits_{k=1}^{\left\lfloor\dfrac{n}{p}\right\rfloor}\left\lfloor\dfrac{n}{pk}\right\rfloor\left\lfloor\dfrac{m}{pk}\right\rfloor\mu(k)\\
&= \sum\limits_{k=1}^{\left\lfloor\dfrac{n}{2}\right\rfloor}\sum\limits_{p\in\mathbb P\cap[1, \left\lfloor\dfrac{n}{k}\right\rfloor]}\left\lfloor\dfrac{n}{pk}\right\rfloor\left\lfloor\dfrac{m}{pk}\right\rfloor\mu(k)\\
&= \sum\limits_{t=1}^n\left\lfloor\dfrac{n}{t}\right\rfloor\left\lfloor\dfrac{m}{t}\right\rfloor\sum\limits_{p ~\vert ~t, p\in\mathbb P\cap[1, n]} \mu\left(\dfrac{t}{p}\right)
\end{aligned}
$$
我们观察到后面这个 $F(t) = \displaystyle\sum\limits_{d ~\vert ~t, d\in\mathbb P} \mu\left(\dfrac{t}{d}\right)$ 看起来非常积性，然而并非。比如：$F(2)F(3)\ne F(6)$。那咋办？
有一个非常 naive 的想法，在埃氏筛的过程中，对于每个质数 $p$，给它的每个倍数 $kp$ 的值 $F(kp)$ 加上 $\mu(k)$。这显然是对的，只需要反过来考虑贡献就可以了，于是我们就会 $\Omicron(n \log \log n + T\sqrt{n})$ 了，显然能过。
当然我们还有更快的做法。虽然 $F(n)$ 不是积性函数，但是 $F(n)$ 居然是可以用线性筛的！我们考虑分类讨论。
1. 当 $n = 1$ 时，显然 $F(n) = 0$；
2. 当 $n \in \mathbb P$ 时，$F(n) = \mu\left(\dfrac{n}{n}\right) = \mu(1) = 1$；
3. 当 $n \not \in \{1\} \cup \mathbb P$ 时，我们考虑线性筛的过程（设现在枚举到 $i$，$p$ 是存储质数的数组，正在筛 $n= i \times p_j$）：
- 当 $p_j~\vert~i$ 时，有 $p_j^2 ~\vert~ n$，而由于 $p_j$ 是质数，当 $d \ne p_j$ 时 $\mu\left(\dfrac{n}{d}\right) = 0$（n 含有 $p_j^2$ 的因子），仅当 $d = p_j$ 时才有取值，因此 $F(n) = \mu\left(\dfrac{n}{p_j}\right) = \mu(i)$；
- 否则，$i$ 和 $p_j$ 一定互质，利用 $\mu(n)$ 是积性函数的性质，$F(n) = \displaystyle\sum\limits_{d ~\vert ~n, d\in\mathbb P} \mu\left(\dfrac{ip_j}{d}\right) = \left(\displaystyle\sum\limits_{d ~\vert ~i, d\in\mathbb P} \mu\left(\dfrac{ip_j}{d}\right)\right) + \mu\left(\dfrac{ip_j}{p_j}\right) = \mu(p_j)\left(\displaystyle\sum\limits_{d ~\vert ~i, d\in\mathbb P} \mu\left(\dfrac{i}{d}\right)\right) + \mu(i) = \mu(i) - F(i)$。
于是就可以线性筛了，因此本题能够做到 $\Omicron(n + T\sqrt{n})$，[但是为啥还是跑的这么慢](/record/288418942)。
----------------------
### [例题 4：洛谷 P2260 [清华集训 2012] 模积和](/problem/P2260)
为了防止你学 Möbius 反演学魔怔了，看到 $\displaystyle\sum$ 就想 Möbius 反演~~反了你了~~，于是在这里放了一道不用 Möbius 反演的数论分块。
式子里有个 $i \ne j$ 不是很好处理，考虑拆出来，然后化成整除形式。推式子的时候暂且不考虑取模，假设 $n \le m$。
$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n \bmod i)(m \bmod j)[i \ne j]
&= \left(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n \bmod i)(m \bmod j)\right) - \left(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n \bmod i)(m \bmod j)[i = j]\right)\\
&= \left(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(n \bmod i)(m \bmod j)\right) - \left(\sum\limits_{i=1}^n(n \bmod i)(m \bmod i)\right)\\
&= \left(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\left(n - i\left\lfloor\dfrac{n}{i}\right\rfloor\right)\left(m - j\left\lfloor\dfrac{m}{j}\right\rfloor\right)\right) - \left(\sum\limits_{i=1}^n\left(n - i\left\lfloor\dfrac{n}{i}\right\rfloor\right)\left(m - i\left\lfloor\dfrac{m}{i}\right\rfloor\right)\right)\\
&= \left(\sum\limits_{i=1}^n\left(n - i\left\lfloor\dfrac{n}{i}\right\rfloor\right)\right)\left(\sum\limits_{j=1}^m\left(m - j\left\lfloor\dfrac{m}{j}\right\rfloor\right)\right) - \left(\sum\limits_{i=1}^n\left(n - i\left\lfloor\dfrac{n}{i}\right\rfloor\right)\left(m - i\left\lfloor\dfrac{m}{i}\right\rfloor\right)\right)\\
&= \left(\sum\limits_{i=1}^n \left(n - i\left\lfloor\dfrac{n}{i}\right\rfloor\right)\right)\left(\sum\limits_{i=1}^m \left(m - i\left\lfloor\dfrac{m}{i}\right\rfloor\right)\right) - \left(\sum\limits_{i=1}^n\left(n - i\left\lfloor\dfrac{n}{i}\right\rfloor\right)\left(m - i\left\lfloor\dfrac{m}{i}\right\rfloor\right)\right)\\
&= \left(n^2-\sum\limits_{i=1}^n i\left\lfloor\dfrac{n}{i}\right\rfloor\right)\left(m^2-\sum\limits_{i=1}^m i\left\lfloor\dfrac{m}{i}\right\rfloor\right) - n^2m + n\left(\sum\limits_{i=1}^n i\left\lfloor\dfrac{m}{i}\right\rfloor\right)+m\left(\sum\limits_{i=1}^n i\left\lfloor\dfrac{n}{i}\right\rfloor\right)-\left(\sum\limits_{i=1}^n i^2\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor\right)\\
\end{aligned}
$$
很好，看起来每一项都很容易数论分块了。但是有一点要注意，我们如何计算 $\displaystyle\sum\limits_{i=1}^n i^2$？
学过小学奥数的应该都知道一个熟知结论：
$$\sum\limits_{i=1}^n i^2=\dfrac{n(n+1)(2n+1)}{6}$$
:::success[构造与证明]{open}
数学归纳法是显然的，但是我和你们一样也想知道这个式子是怎么从头推出来的。
首先处理这种前缀和的式子有一种惯用的手法。
令 $f(k) = k^2$，我们所求的即为 $f(k)$ 的前缀和。我们考虑构造 $g(k)$ 使得 $g(k + 1) - g(k) = f(k)$。这样有什么好处呢？
把这个式子代回原来的求和：
$$
\begin{aligned}
\sum\limits_{i=1}^n i^2
&= \sum\limits_{k=1}^n f(k)\\
&= \sum\limits_{k=1}^n \left(g(k + 1) - g(k)\right)\\
&= g(n + 1) - g(1)
\end{aligned}
$$
容易发现这样能够使得相邻两项互相抵消，只留下两项 $g(n + 1) - g(1)$，变得容易计算。
因此我们只需要考虑构造 $g(k)$ 即可。由于 $f(k)$ 是一个二次多项式，因此我们猜测 $g(k)$ 是一个三次多项式。我们使用待定系数法，设 $g(k) = ak^3 + bk^2 + ck + d$，我们有：
$$
\begin{aligned}
g(k+1)-g(k)
&= a(3k^2+3k+1)+b(2k+1)+c\\
&= 3ak^2 + (3a+2b)k + (a+b+c)\\
&= k^2
\end{aligned}
$$
比较系数容易得出：
$$
\begin{cases}
3a=1\\
3a+2b=0\\
a+b+c=0\\
\end{cases}
$$
因此 $g(k) = \dfrac{1}{3}k^3-\dfrac{1}{2}k^2+\dfrac{1}{6}k+d$（$d$ 可以为任意值）是一个合法的构造。这里我们取 $d = 0$，即 $g(k) = \dfrac{1}{3}k^3-\dfrac{1}{2}k^2+\dfrac{1}{6}k = \dfrac{k(k-1)(2k-1)}{6}$。
代回原求和式，即：
$$
\begin{aligned}
\sum\limits_{i=1}^n i^2
&= \sum\limits_{k=1}^n f(k)\\
&= \sum\limits_{k=1}^n \left(g(k + 1) - g(k)\right)\\
&= g(n + 1) - g(1)\\
&= \dfrac{n(n+1)(2n+1)}{6} - \dfrac{1 \times 0 \times 1}{6}\\
&= \dfrac{n(n+1)(2n+1)}{6}
\end{aligned}
$$
证毕。
当然我们可以沿用上述思路，直接算 $\displaystyle \sum\limits_{i=l}^r i^2$：
$$
\begin{aligned}
\sum\limits_{i=l}^r i^2
&= \sum\limits_{k=l}^r f(k)\\
&= \sum\limits_{k=l}^r \left(g(k + 1) - g(k)\right)\\
&= g(r + 1) - g(l)\\
&= \dfrac{r(r+1)(2r+1)}{6} - \dfrac{l(l - 1)(2l - 1)}{6}\\
&= \dfrac{r(r+1)(2r+1) - l(l - 1)(2l - 1)}{6}
\end{aligned}
$$
或者说你直接差分也行。
:::
有了这个，那我们直接数论分块就好了。时间复杂度 $\Omicron(\sqrt{n} + \sqrt{m})$，可以轻松通过，[跑得飞快](/record/288521690)。
----------------------
上面这些题，不同循环枚举变量都是分开的，那如果 $i, j$ “粘”在一起该怎么处理呢？
----------------------
### [例题 5：洛谷 P3327 [SDOI2015] 约数个数和](/problem/P3327)
题目让我们求 $\displaystyle\sum\limits_{i=1}^n\sum\limits_{j=1}^m d(ij)$，$i, j$ 被放在一个括号里没法直接拆，怎么办呢？
我们考虑一下 $d(ij)$ 能表示成什么。由于约数函数 $d(n)$ 是积性函数，我们可以对于单个质数 $p$ 考虑：设 $p$ 在 $i$ 中指数为 $a$，在 $j$ 中指数为 $b$。显然此时 $ij$ 的因数中 $p$ 的指数有 $a + b + 1$ 种情况。考虑枚举 $i$ 的因数 $x$ 和 $j$ 的因数 $y$，但是此时 $xy$ 中 $p$ 的指数有 $(a + 1)(b + 1)$ 种情况，这显然是不对的。怎么凑出 $a + b + 1$？我们只需要限定 $x, y$ 中只能有至多一个数有 $p$ 因子即可，这等价于 $\gcd(x, y) = 1$。
所以我们有：
$$d(ij) = \sum\limits_{x~\vert~i}\sum\limits_{y~\vert~j}[\gcd(x, y) = 1]$$
我知道这有点难理解，我也有点理解不了，你可以多读几遍，~~或者想我一样想不懂就背下来~~，这已经是我能想到最通俗易懂的一种解释了。
假装 $n \le m$，我们就可以开始愉快地推式子了：
$$
\begin{aligned}
\sum\limits_{i=1}^n\sum\limits_{j=1}^m d(ij)
&= \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x~\vert~i}\sum\limits_{y~\vert~j}[\gcd(x, y) = 1]\\
&= \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x~\vert~i}\sum\limits_{y~\vert~j}\sum\limits_{d~\vert~\gcd(x, y)} \mu(d)\\
&= \sum\limits_{d=1}^n\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor}\sum\limits_{x=1}^{\left\lfloor\dfrac{n}{di}\right\rfloor}\sum\limits_{y=1}^{\left\lfloor\dfrac{m}{dj}\right\rfloor}\mu(d)\\
&= \sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\left\lfloor\dfrac{n}{di}\right\rfloor\sum\limits_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor}\left\lfloor\dfrac{m}{dj}\right\rfloor &\begin{cases}p\gets\left\lfloor\dfrac{n}{d}\right\rfloor\\q\gets\left\lfloor\dfrac{m}{d}\right\rfloor\end{cases}\\
&= \sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{p}\left\lfloor\dfrac{p}{i}\right\rfloor\sum\limits_{j=1}^{q}\left\lfloor\dfrac{q}{j}\right\rfloor&S(n)\gets\sum\limits_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor\\
&= \sum\limits_{d=1}^n\mu(d)S(p)S(q)\\
&= \sum\limits_{d=1}^n\mu(d)S(\left\lfloor\dfrac{n}{d}\right\rfloor)S(\left\lfloor\dfrac{m}{d}\right\rfloor)
\end{aligned}
$$
注意到 $\mu(n)$ 可以线性筛预处理，$S(n)$ 我们可以用 $\Omicron(n\sqrt n)$ 数论分块预处理，然后再假装 $S(n)$ 是一个数论函数，回答询问的时候，再用一个数论分块进行计算即可，~~什么数论分块套数论分块~~。
时间复杂度为 $\Omicron((n + T) \sqrt n)$，可恶的出题人只开了 1s，很有可能过不去。
我们注意到，其实有 $\displaystyle\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor = \sum\limits_{i=1}^nd(i)$。
:::success[证明]
我们考虑发动传统技能：
我们考虑等式左边干了啥。我们发现左边其实是在数有序数对 $(i, j)$（$1 \le i \le n$，$1 \le j \le \left\lfloor\dfrac{n}{i}\right\rfloor$）的个数。也就是 $1 \le ij \le n$ 的有序数对 $(i, j)$ 个数。
然后我们考虑等式右边干了啥。首先右边显然数了有序数对 $(d, i)$（$1 \le i \le n$，$d ~\vert~ i$）的数量。但是这里有个整除不好处理，考虑转换成倍数形式。我们转为枚举 $d$，令 $i = kd$，于是等价于数有序数对 $(d, k)$（$1\le kd \le n$）。
我们发现数有序数对 $(i, j)$（$1 \le ij \le n$）的个数和数有序数对 $(d, k)$（$1\le i = kd \le n$）是等价的，证毕。
:::
于是用线性筛预处理 $d(n)$ 可以做到 $O(n + T\sqrt n)$，[轻松通过](/record/288576830)。
----------------------
### [例题 6：洛谷 P4619 [SDOI2018] 旧试题](/problem/P4619)
做了这么多题，我们就用这道题目来总结一下 Möbius 反演的各种惯用方法吧。
看到这个 $d(ijk)$ 你是不是想到了什么？对，可以照葫芦画瓢地展开：
$$
d(ijk) = \sum\limits_{x~\vert~i}\sum\limits_{y~\vert~j}\sum\limits_{z~\vert~k}[\gcd(x,y)=1][\gcd(y,z)=1][\gcd(z,x)=1]
$$
然后我们带回原式，假装 $A \le B \le C$，进行 Möbius 反演（推导过程忽略模数）：
$$
\begin{aligned}
\sum\limits_{i=1}^A\sum\limits_{j=1}^B\sum\limits_{k=1}^Cd(ijk)
&= \sum\limits_{i=1}^A\sum\limits_{j=1}^B\sum\limits_{k=1}^C\sum\limits_{x~\vert~i}\sum\limits_{y~\vert~j}\sum\limits_{z~\vert~k}[\gcd(x,y)=1][\gcd(y,z)=1][\gcd(z,x)=1]\\
&= \sum\limits_{i=1}^A\sum\limits_{j=1}^B\sum\limits_{k=1}^C\sum\limits_{x~\vert~i}\sum\limits_{y~\vert~j}\sum\limits_{z~\vert~k}\sum\limits_{a~\vert~\gcd(x,y)}\sum\limits_{b~\vert~\gcd(y,z)}\sum\limits_{c~\vert~\gcd(z,x)}\mu(a)\mu(b)\mu(c)\\
&= \sum\limits_{i=1}^A\sum\limits_{x~\vert~i}\sum\limits_{j=1}^B\sum\limits_{y~\vert~j}\sum\limits_{k=1}^C\sum\limits_{z~\vert~k}\sum\limits_{a~\vert~\gcd(x,y)}\sum\limits_{b~\vert~\gcd(y,z)}\sum\limits_{c~\vert~\gcd(z,x)}\mu(a)\mu(b)\mu(c)\\
&= \sum\limits_{x=1}^A\sum\limits_{i=1}^{\left\lfloor\dfrac{A}{x}\right\rfloor}\sum\limits_{y=1}^B\sum\limits_{j=1}^{\left\lfloor\dfrac{B}{y}\right\rfloor}\sum\limits_{z=1}^C\sum\limits_{k=1}^{\left\lfloor\dfrac{C}{z}\right\rfloor}\sum\limits_{a~\vert~\gcd(x,y)}\sum\limits_{b~\vert~\gcd(y,z)}\sum\limits_{c~\vert~\gcd(z,x)}\mu(a)\mu(b)\mu(c)\\
&= \sum\limits_{x=1}^A\sum\limits_{y=1}^B\sum\limits_{z=1}^C\left\lfloor\dfrac{A}{x}\right\rfloor\left\lfloor\dfrac{B}{y}\right\rfloor\left\lfloor\dfrac{C}{z}\right\rfloor\sum\limits_{a~\vert~\gcd(x,y)}\sum\limits_{b~\vert~\gcd(y,z)}\sum\limits_{c~\vert~\gcd(z,x)}\mu(a)\mu(b)\mu(c)\\
&= \sum\limits_{x=1}^A\sum\limits_{y=1}^B\sum\limits_{z=1}^C\sum\limits_{a~\vert~x,a~\vert~y}\sum\limits_{b~\vert~y,b~\vert~z}\sum\limits_{c~\vert~z,c~\vert~x}\left\lfloor\dfrac{A}{x}\right\rfloor\left\lfloor\dfrac{B}{y}\right\rfloor\left\lfloor\dfrac{C}{z}\right\rfloor\mu(a)\mu(b)\mu(c)\\
&= \sum\limits_{a=1}^A\sum\limits_{b=1}^B\sum\limits_{c=1}^C\sum\limits_{a~\vert~x,c~\vert~x}\sum\limits_{a~\vert~y,b~\vert~y}\sum\limits_{b~\vert~z,c~\vert~z}\left\lfloor\dfrac{A}{x}\right\rfloor\left\lfloor\dfrac{B}{y}\right\rfloor\left\lfloor\dfrac{C}{z}\right\rfloor\mu(a)\mu(b)\mu(c)\\
&= \sum\limits_{a=1}^A\sum\limits_{b=1}^B\sum\limits_{c=1}^C\mu(a)\mu(b)\mu(c)\sum\limits_{\operatorname{lcm}(c,a)~\vert~x}\sum\limits_{\operatorname{lcm}(a,b)~\vert~y}\sum\limits_{\operatorname{lcm}(b,c)~\vert~z}\left\lfloor\dfrac{A}{x}\right\rfloor\left\lfloor\dfrac{B}{y}\right\rfloor\left\lfloor\dfrac{C}{z}\right\rfloor&\begin{cases}u\gets\dfrac{x}{\operatorname{lcm}(c,a)}\\v\gets\dfrac{y}{\operatorname{lcm}(a,b)}\\w\gets\dfrac{z}{\operatorname{lcm}(b,c)}\end{cases}\\
&= \sum\limits_{a=1}^A\sum\limits_{b=1}^B\sum\limits_{c=1}^C\mu(a)\mu(b)\mu(c)\sum\limits_{u=1}^{\left\lfloor\dfrac{A}{\operatorname{lcm}(c,a)}\right\rfloor}\sum\limits_{v=1}^{\left\lfloor\dfrac{B}{\operatorname{lcm}(a,b)}\right\rfloor}\sum\limits_{w=1}^{\left\lfloor\dfrac{C}{\operatorname{lcm}(b,c)}\right\rfloor}\left\lfloor\dfrac{A}{u\operatorname{lcm}(c,a)}\right\rfloor\left\lfloor\dfrac{B}{v\operatorname{lcm}(a,b)}\right\rfloor\left\lfloor\dfrac{C}{w\operatorname{lcm}(b,c)}\right\rfloor\\
&= \sum\limits_{a=1}^A\sum\limits_{b=1}^B\sum\limits_{c=1}^C\mu(a)\mu(b)\mu(c)\sum\limits_{u=1}^{\left\lfloor\dfrac{A}{\operatorname{lcm}(c,a)}\right\rfloor}\left\lfloor\dfrac{{\left\lfloor\dfrac{A}{\operatorname{lcm}(c,a)}\right\rfloor}}{u}\right\rfloor\sum\limits_{v=1}^{\left\lfloor\dfrac{B}{\operatorname{lcm}(a,b)}\right\rfloor}\left\lfloor\dfrac{{\left\lfloor\dfrac{B}{\operatorname{lcm}(a,b)}\right\rfloor}}{v}\right\rfloor\sum\limits_{w=1}^{\left\lfloor\dfrac{C}{\operatorname{lcm}(b,c)}\right\rfloor}\left\lfloor\dfrac{{\left\lfloor\dfrac{C}{\operatorname{lcm}(b,c)}\right\rfloor}}{w}\right\rfloor&S(n)\gets\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor\\
&= \sum\limits_{a=1}^A\sum\limits_{b=1}^B\sum\limits_{c=1}^C\mu(a)\mu(b)\mu(c)S(\left\lfloor\dfrac{A}{\operatorname{lcm}(c,a)}\right\rfloor)S(\left\lfloor\dfrac{B}{\operatorname{lcm}(a,b)}\right\rfloor)S(\left\lfloor\dfrac{C}{\operatorname{lcm}(b,c)}\right\rfloor)
\end{aligned}
$$
根据我们先前的结论，$\displaystyle S(n) = \sum\limits_{i=1}^nd(i)$，可以线性筛预处理。
其实这道题的推式子部分到这里已经结束了，接下来我们考虑一下怎么算。
:::info[暴力]
我会暴力枚举三元组！
那你前面在反演什么？你这不白反演了。
时间复杂度 $\Omicron(n^3)$，期望得分 $0$ 分。
:::
:::success[正解]{open}
观察到 $\mu(a)\mu(b)\mu(c)$ 很容易是 $0$，因此实际上对答案有贡献的式子不多。
我们可以考虑图论建模。
- 考虑有什么点：显然 $\mu(u) = 0$ 的点 $u$ 对答案没有贡献，把这些点扔了。
- 考虑有什么边：对于结点 $u, v$，如果 $\operatorname{lcm}(u, v) \le A$（不然贡献为 $0$），我们就在他们之间连边。
考虑怎么连边。我们可以枚举 $\gcd(u, v)$，然后枚举互质的两个 $x, y$（$x < y$，$xy\gcd(u,v) = \operatorname{lcm}(u, v \le A$），在 $x\gcd(u,v)$ 和 $y\gcd(u,v)$ 之间连边。
显然边数是 $\Omicron(m) = \Omicron(n \log^2 n)$ 级别的。但是如果你实际建一个图你会发现严重建不满，图非常稀疏，$m$ 只有大约 $7.1 \times 10^5$。
然后这个题就变成了一个无向图三元环计数问题，可以做到 $\Omicron(m\sqrt m)$。注意一个三元环要六个排列分别统计，然后就做完了。
:::
作为一道黑题，难度还是很高的。
### 总结
Möbius 反演常用化简方法：
1. 含有 $\gcd$ 的式子，枚举 $\gcd$ 把内层化成一个计数；
2. 枚举某个数的因数，可以直接转换成枚举上下界；
3. 交换求和顺序；
4. 利用 Möbius 反演的**性质一**，把 Iverson 括号拆成求和形式；
5. 基于 1 和 4 的扩展，可以枚举 Iverson 括号里的东西，把 Iverson 括号转换成形如 $[f(n)=1]$ 的形式；
6. 把式子拆成可以数论分块的形式，加速求和；
7. 有时候多换元能够更加容易观察出式子的性质。
希望这篇学习笔记能够更好地帮助你理解 Möbius 反演！~~在省选赛场上爆切紫题~~。
## 致谢
感谢各个题的题解作者以及 OI-wiki 上 Möbius 反演页面的贡献者们。
感谢音游 Phigros && Rizline 和独立游戏 Rain World 的各个 OST 提供的精神支持（？）