[学习笔记] 莫比乌斯反演及杜教筛
YLWang
·
·
闲话
博主受一位学长启发作过一首诗：
昔人已乘网络去，此地空余网络流。
网络一去不复返，动态规划上树剖。
归约反演推公式，筛法超时卡读优。
日暮Au何处是？分块被卡使人愁。
今日回想起来这首诗，发现自己已经由听说这些算法到了学了这些算法，感慨万千。于是决定写四篇学习笔记来记录。
可以通过点击的方式来访问。
零. 声明
-1. 本文只介绍整数偏序集上的莫比乌斯反演。
0.欢迎标注出处的转载。若有不注明出处的转载将追责。
1.本文默认 p 指一个质数, * 指狄利克雷卷积，\cdot或不写指两个数的乘法。
2.如果本文有笔误请私信作者，如果本文有知识性错误请私信作者并狠狠地D他。
3.阅读本文前请先学习狄利克雷卷积。如果能先学习莫比乌斯函数和欧拉函数相关知识将更加方便理解。
一. 前置知识
0. 常用数论函数
$id(x) = x$.
$e(x) = [x=1]$.
$\mu(x) = [\max\{\alpha_1, ... ,\alpha_k\} \leqslant 1] \times (-1)^k$。其中 $\alpha(i)$ 表示第 $i$ 个质因数的指数。
$\varphi(x) = n \prod_{d|x}(1-\dfrac{1}{d})$.
$d(x) = \sum_{d|x}1$.
$\sigma(x) = \sum_{d|x} d$.
---
## 1. 一些常用性质
$e * F = F. $ 其中 $F$ 是任意数论函数。
$e = \mu * 1.$即 $[n = 1] = \sum_{d|n}\mu(d) $.
这个式子的意义就在于把一些条件（是否等于 $1$）转化为不用条件的 $\mu$ 函数的和。
$id= \varphi * 1. $即 $n = \sum_{d|n}\varphi(d) $.
$\mu * id = \varphi$. 这个式子可以由上面两个式子得到。
$\mu * d = 1$. 这个式子可以反演。
---
## 2. 所谓“数论意义上的莫比乌斯反演”
数论意义上的莫比乌斯反演的式子：
$$
f(n) = \sum_{d|n} g(d)\Leftrightarrow g(n) = \sum_{d|n} f(d) \cdot \mu(\frac{n}{d})
$$
本质就是如下一个显然的式子。
$$
f = g * 1\Leftrightarrow g = f * \mu
$$
怎么证？把左式两边卷一个 $\mu$ 即可。
---
## 3.线性筛
线性筛是用来求出 $\mu$ 和 $\varphi$ 等积性函数的。
```cpp
int vis[MAXN], prime[MAXN], mu[MAXN], phi[MAXN], cnt = 0;
void init(int n) {
mu[1] = phi[1] = 1;
for(int i = 2; i <= n; i++) {
if(!vis[i]) prime[++cnt] = i, mu[i] = -1, phi[i] = i - 1;
for(int j = 1; j <= cnt && i* prime[j] <= n; j++) {
vis[i * prime[j]] = 1;
if(i % prime[j] != 0) {
mu[i * prime[j]] = -mu[i];
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
} else {
mu[i * prime[j]] = 0;
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
```
这里我们保证每个数都被其最小质因子而筛除。在代码中体现为 $prime_j$.
所以不难推出为什么这么筛了。
注意一下筛某些数论函数（例如 $d$, $\sigma$）时需要记录有关一个数最小质因子的信息。
---
# 二. 莫比乌斯反演基础例题
我们主要用它来解决 $\gcd$ 的和这一类题目。常见的方法就是提前枚举因数等。
以下例题全部默认 $n \leqslant 10^5$, 若有多测则 $T \leqslant 10^4$, 。
---
## 例0
多测，求：
$$
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i, j) = 1]
$$
这道题是大部分基础莫比乌斯反演的根源。
我们考虑直接把$[\gcd(i, j) = 1]$用上边提到的方法代换。这个时候的代换方法是$e = 1*\mu$. 然后把所得到的 $d$ 提前枚举，将 $i, j$ 用 $di^{'}, dj^{'}$ 代换即可。
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i, j) = 1]
&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d|\gcd(i, j)}\mu(d)
\\&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}\sum\limits_{d|i, d|j}\mu(d)
\\ &= \sum\limits_{d=1}^{n} \mu(d) \sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor } \sum\limits_{j=1}^{\lfloor \frac{n}{d} \rfloor} 1
\\ &= \sum\limits_{d=1}^{n} \mu(d) \cdot \lfloor\frac{n}{d}\rfloor ^ 2
\end{aligned}
$$
这之后使用线筛预处理，整除分块计算就可以了。
---
## 例1
$x$ 为一个给定参数，多测，求：
$$
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i, j) = x]
$$
我们考虑直接把 $[\gcd(i, j) = x]$ 转化成 $i = x \cdot i^{'}, j = x \cdot j^{'}.$ 然后使用例0的方法即可。
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i, j) = x]
&=\sum\limits_{i=1}^{\lfloor \frac{n}{x} \rfloor} \sum\limits_{j=1}^{\lfloor \frac{n}{x} \rfloor} [\gcd(i, j) = 1]
\\&= \sum\limits_{d=1}^{\lfloor\frac{n}{x}\rfloor}\mu(d) \cdot \lfloor\frac{n}{dx}\rfloor ^ 2
\end{aligned}
$$
这之后使用线筛预处理，整除分块计算就可以了。
---
## 例2
多测，求：
$$
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i, j)
$$
### 法1：
常规推导. 我们先枚举一手最大公约数就可以转化为例1的形式。
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i, j)
&= \sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i, j)=d]
\\ &= \sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum\limits_{j=1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i, j)=1]
\\ &= \sum\limits_{d=1}^{n}d\sum\limits_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \cdot \lfloor\frac{\lfloor\frac{n}{d}\rfloor}{t} \rfloor ^ 2
\\ &= \sum\limits_{d=1}^{n}d\sum\limits_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \cdot \lfloor \frac{n}{dt} \rfloor ^ 2
\end{aligned}
$$
我们推到这儿就会有两种不同求法。
第一种是两次整除分块。我们先分块外面的第一重，再分块求里面的第二重就可以了。复杂度因为作者学识浅薄不会算，粗略积一下分应该是 $O(n^{\frac{3}{4}})$ 的。
什么？你说右边这东西分母上有个 $d$ 不能分块？
什么？你说倒数第二步怎么推出结果的？
那么您应该是仔细思考了。下面这个式子是一个定理，证明不难。有兴趣的话可以自行证明。
$$
\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{t} \rfloor = \lfloor\frac{n}{dt} \rfloor
$$
第二种是发掘性质。经验丰富的反演怪们一定会一眼就看出来这是个卷积形式。
我们把 $dt$ 用 $k$ 带进去。
$$
\begin{aligned}
\sum\limits_{d=1}^{n}d\sum\limits_{t=1}^{\lfloor \frac{n}{d} \rfloor} \mu(t) \cdot \lfloor \frac{n}{dt} \rfloor ^ 2
&= \sum\limits_{k=1}^{n}\lfloor \frac{n}{k} \rfloor ^ 2\sum\limits_{d|k}d \cdot \mu(\frac{k}{d})
\\ &= \sum\limits_{k=1}^{n}\lfloor \frac{n}{k} \rfloor^ 2\varphi(k)
\end{aligned}
$$
就得出了一个可以快速计算的式子。
最后一步是因为 $\mu * id = \varphi$.
**但是，如果你足够熟悉数论函数间的联系，你可以用非常快的方法解决这题。**
### 法2:
我们考虑直接把 $\gcd(i, j)$ 用上边提到的方法代换。这个时候的代换方法是$id = 1*\varphi$.
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \gcd(i, j)
&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \sum\limits_{d|\gcd(i, j)}\varphi(d)
\\ &= \sum\limits_{d=1}^{n} \varphi(d) \cdot \lfloor\frac{n}{d}\rfloor ^ 2
\end{aligned}
$$
是不是感觉眼前一亮？
### 推论：
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(gcd(i, j)) = \sum\limits_{d=1}^{n}\lfloor\frac{n}{d}\rfloor^2(f*u)(d)
\end{aligned}
$$
---
## 例3 [P3327 [SDOI2015]约数个数和](https://www.luogu.com.cn/problem/P3327)
稍微改一下题，把 $m$ 改成 $n$.
这个题需要一点思维。我们尽量把这个问题往 $\gcd$ 上面靠。
我们不难想到一个式子。
$$
d(i \cdot j) = \sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x, y)=1]
$$
那么，还是很套路把枚举因数怼到前面即可。
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} d(i\cdot j)
&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x, y)=1]
\\ &= \sum\limits_{x=1}^{n} \sum\limits_{y=1}^{n}[\gcd(x, y)=1]\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{y}\rfloor} 1
\\ &=\sum\limits_{x=1}^{n} \sum\limits_{y=1}^{n}[\gcd(x, y)=1]\lfloor\frac{n}{x}\rfloor\lfloor\frac{n}{y}\rfloor
\\ &=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}[\gcd(i, j)=1]\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor
\\ &=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}\sum\limits_{d|i,d|j}\mu(d) \lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{j}\rfloor
\\ &=\sum\limits_{d=1}^{n}\mu(d) \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{id}\rfloor\lfloor\frac{n}{jd}\rfloor
\\ &=\sum\limits_{d=1}^{n}\mu(d) \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{i} \rfloor\rfloor\lfloor\frac{\lfloor\frac{n}{d}\rfloor}{j} \rfloor\rfloor
\end{aligned}
$$
整除分块+预处理即可。
---
## 例4 [P1829 [国家集训队]Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
稍微改一下题，把 $m$ 改成 $n$.
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} lcm(i, j)
&= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \frac{i \cdot j}{\gcd(i, j)}
\\ &= \sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} \frac{id \cdot jd}{d} \cdot [\gcd(i, j)=1]
\\ &= \sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} i \cdot j \cdot d \sum\limits_{t|i, t|j}\mu(t)
\\ &= \sum\limits_{d=1}^{n}d\sum\limits_{t=1}^{\lfloor \frac{n}{d} \rfloor} t^2 \mu(t)\sum\limits_{i=1}^{\lfloor\frac{n}{dt}\rfloor} \sum\limits_{j=1}^{\lfloor\frac{n}{dt}\rfloor} i \cdot j
\end{aligned}
$$
就推完了。
---
## 例5 [P3768 简单的数学题](https://www.luogu.com.cn/problem/P3768)
$$
\begin{aligned}
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} i\cdot j\cdot \gcd(i, j)
&= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}i \cdot j\cdot \sum\limits_{d|i, d|j}\varphi(d) \\
&=\sum\limits_{d=1}^{n}\varphi(d) \cdot d^2\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{n}{d} \rfloor}i \cdot j \\
&=\sum\limits_{d=1}^{n}\varphi(d) \cdot d^2\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}i\sum\limits_{j=1}^{\lfloor \frac{n}{d} \rfloor} j \\
\end{aligned}
$$
后面那个玩意显然是可以直接求的。那么杜教筛+整除分块即可。
---
# 三. 莫比乌斯反演进阶例题
这类题我将会给出代码实现。
## 例0 [P3704 [SDOI2017]数字表格](https://www.luogu.com.cn/problem/P3704)
$f$ 是斐波那契数列。$f_0 = 0$。求
$$
\prod\limits_{i=1}^{n} \prod\limits_{i=1}^{m} f_{\gcd(i,j)}.
$$
解：不妨假设 $m = n.
\begin{aligned}
\prod\limits_{i=1}^{n} \prod\limits_{i=1}^{n} f_{\gcd(i,j)}
&= \prod\limits_{d=1}^{n} \prod\limits_{i=1}^{n} \prod\limits_{i=1}^{n} f_{d} ^{[\gcd(i,j)=d]}
\\&= \prod\limits_{d=1}^{n} f_d ^{\sum_{i=1}^{n} \sum_{j=1}^{n}[\gcd(i,j)=d]}
\\&= \prod\limits_{d=1}^{n} f_d ^{\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t) \cdot \lfloor\frac{n}{dt}\rfloor ^ 2}
\end{aligned}
我们发现似乎没法预处理 f 的次方前缀和。于是单次处理就是 n \sqrt{n} 的。原地升天。
那么我们就考虑套路地枚举 k = dt 呗。
\begin{aligned}
\prod\limits_{d=1}^{n} f_d ^{\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t) \cdot \lfloor\frac{n}{dt}\rfloor ^ 2}
&= \prod\limits_{k=1}^{n}\prod\limits_{d|k}f_d^{\mu{(\frac{k}{d})}\lfloor\frac{n}{k}\rfloor ^ 2}
\\&= \prod\limits_{k=1}^{n}(\prod\limits_{d|k}f_d^{\mu{(\frac{k}{d})}})^{\lfloor\frac{n}{k}\rfloor ^ 2}
\end{aligned}
注意做推式子题的时候不要迷失在式子中。时刻要停下来想一想是否可以算了。
我们发现外层是一个数论分块形式。内层这种整除一看就是可以枚举倍数O(n \operatorname{ln} n)预处理的。
最后的结果就是
\prod\limits_{k=1}^{n}(\prod\limits_{d|k}f_d^{\mu{(\frac{k}{d})}})^{\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor}
干就完了。复杂度根据实现方式而定。
代码链接：https://www.luogu.com.cn/paste/wo3fib89
例1 P4240 毒瘤之神的考验
\begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \varphi(ij)
&= \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}
\\&= \sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \frac{\varphi(i)\varphi(j)d[\gcd(i,j)=d]}{\varphi(d)}
\\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m }\varphi(i)\varphi(j)[\gcd(i,j)=d]
\\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\cdot \sum\limits_{i=1}^{\lfloor\frac{n}{dt}\rfloor }\sum\limits_{j=1}^{\lfloor\frac{m}{dt}\rfloor }\varphi(idt)\varphi(jdt)
\\&= \sum\limits_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\cdot \sum\limits_{i=1}^{\lfloor\frac{n}{dt}\rfloor }\sum\limits_{j=1}^{\lfloor\frac{m}{dt}\rfloor }\varphi(idt)\varphi(jdt)
\\&= \sum\limits_{k=1}^{n}\sum\limits_{d|k} \frac{d\cdot\mu(\frac{k}{d})}{\varphi(d)} \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor }\varphi(ik)\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor }\varphi(jk)
\end{aligned}
令
\begin{aligned}
f(n) = \sum\limits_{d|n} \frac{d\cdot\mu(\frac{k}{d})}{\varphi(d)}
\end{aligned}
则可以套路地枚举倍数预处理出来。这一部分的复杂度是 O(n \operatorname{ln} n).
再令
\begin{aligned}
g(k, n) = \sum\limits_{i=1}^{n}\varphi(ik)
\end{aligned}
我们有递推式
\begin{aligned}
g(i, j) = g(i, j-1) +\varphi(ij)
\end{aligned}
因为k\cdot n \leqslant 10^5, 所以这一部分的复杂度为 O(n \operatorname{ln} n).
我们把原式用 f 与 g 代入。
\begin{aligned}
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \varphi(ij)
&=\sum\limits_{k=1}^{n}f(k)\cdot g(k, \lfloor\frac{n}{k}\rfloor )\cdot g(k,\lfloor\frac{m}{k}\rfloor )
\end{aligned}
然后你会发现这个时候 g 里面是带 k 的不能整除分块。
还是很套路的把整个式子用参数表示出来。令：
\begin{aligned}
t(a, b,n) = \sum\limits_{k=1}^{n}f(k)\cdot g(k, a)\cdot g(k, b)
\end{aligned}
那么最终的结果就是一个差分形式（其实 l 和 r 是整除分块的两端。）
\begin{aligned}
\sum\limits_{\lfloor\frac{n}{l}\rfloor = \lfloor\frac{n}{r}\rfloor \& \lfloor\frac{m}{l}\rfloor = \lfloor\frac{m}{r}\rfloor} t(\lfloor\frac{n}{r}\rfloor, \lfloor\frac{m}{r}\rfloor,r) - t(\lfloor\frac{n}{r}\rfloor, \lfloor\frac{m}{r}\rfloor,l)
\end{aligned}
那么问题就是如何求出 t 数组了。容易发现直接全部预处理会 T 到原地升天。
我们发现这实际上是一个预处理和查询的平衡，所以引出根号分治那一套理论。
因为我们发现，l 和 r 越大，相同一段长度就越大，暴力的复杂度就相对越劣（意思就是用整除分块处理越快）。我们考虑在 l 和 r 较小的时候暴力，否则预处理。
我们设一个阈值 S，将所有 t(1,1,1) - t(S,S,n) 的 t 值预处理出来。
预处理的式子就是
t(j,k,i)=t(j,k,i-1) + f(i)\cdot g(i, j)\cdot g(i, k)
然后查询的时候，对于所有 \lfloor\dfrac{n}{r}\rfloor \leqslant S 可以直接查询。否则，可得知 r \leqslant \lfloor\dfrac{n}{S}\rfloor。 这个时候就可以暴力计算了.
总的复杂度 O(n \ln n + nB^2 + T(\sqrt{n} +\dfrac{n}{B}))。 至于如何调整 B 参照 Ynoi。
这个题真的是一个好题，可谓是推式子与平衡思想结合的极致。
四. 杜教筛
本节的更新时间和之前有一些脱节。所以语义不连贯的地方请见谅。
杜教筛是用来解决下面这个问题的。
- 求 S(n) = \sum\limits_{i=1}^{n}f(i)。其中 f(i) 为积性函数。
众所周知我们可以 O(n) 线性筛出 f 然后求和。但这都 0202 年了出题人出这么简单肯定是会被喷的。于是就有了一大堆低于现行的筛法出现了。杜教筛就是其中一种。
我们直接推式子。
构造积性函数 h, g 使得 h = f * g。套路地提前因数。
\begin{aligned}
\sum\limits_{i=1}^{n}h(i)
&= \sum\limits_{i=1}^{n}\sum\limits_{d|i}^{n}f(\dfrac{i}{d})g(d)\\
&= \sum\limits_{d=1}^{n}g(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor }f(i)\\
&= \sum\limits_{d=1}^{n}g(d)S(\lfloor\dfrac{n}{d}\rfloor)
\end{aligned}
然后有很妙的一步。
我们不是要算 S(n) 吗，那把这项单独拎出来不就得了。
所以
S(n) = \frac{\sum\limits_{i=1}^{n}h(i) - \sum\limits_{d=2}^{n}g(d)S(\lfloor\dfrac{n}{d}\rfloor)}{g(1)}
于是我们只要能快速算出 h 的前缀和就可以了。
什么叫快速算出 h 的前缀和呢？
比如说 e = \mu * 1 的前缀和就非常的好算。 id = \varphi * 1 的前缀和也非常的好算。
五. 狄利克雷前缀和
前两天刚刚发现有这个科技。是我 naive 了。
正常情况下枚举倍数做贡献是 O(n\ln n) 的。但是这玩意可以优化成 O(n\log\log n)。
我们考虑对质因数分解后的指数做 FMT。则复杂度就是埃氏筛复杂度了。非常清新。