莫比乌斯反演

· · 算法·理论

莫比乌斯反演

0 前言

本文源码目前大约有 45 KiB（主要是公式凑的，实际感觉也不是很长）。可能会造成卡顿。以后可能还会更新。

对莫比乌斯反演的理解前后跨度相当大。有问题请指出。

莫比乌斯反演（Mobius Inversion，本文出于习惯使用莫比乌斯反演而非 Mobius 反演）是计数当中的一个重要技巧。通常与倍数，因数以及 \gcd 有着紧密的联系。

对于一个函数 f(x)，如果我们想求其值，但是很难直接求出，但可以间接的求出其倍数和或因数和函数 g(x)，那么可以考虑使用莫比乌斯反演来快速求出 f(x) 的值。

1 莫比乌斯函数

将 x(x > 0) 质因数分解为 \prod_k p_i^{c_i}，那么我们定义莫比乌斯函数如下：

\mu(x) := \begin{cases} 1, & x = 1, \\ 0, & \exists c_i \geq 2, \\ (-1)^k, & \text{otherwise.} \end{cases}

挖掘一下这个函数的性质。首先我们发现，\mu(x) 是一个积性函数。证明应该比较显然。

请注意分清楚积性函数与完全积性函数的区别。对于式子 f(xy) = f(x)f(y)，积性函数的要求是 \gcd(x,y) = 1, x,y > 0，但是完全积性函数则没有这个限制。

同时我们发现一个至关重要的性质：

\sum_{d \mid n} \mu(d) = \begin{cases} 1, & n = 1, \\ 0, & n \neq 1. \end{cases}

证明可以先考虑把 c_i > 1 给缩起来，然后用二项式定理证明，即，化成 (1+(-1))^x 的形式。

由此我们可以得到一个小性质

\boxed{ [\gcd(i,j) = 1] = \sum_{d \mid \gcd(i,j)} \mu(d) }

我们令上式的 n = \gcd(i,j) 即可说明。

需要注意的是，n 可以为任意值。但是这个式子用的比较多。

由于 \mu(x) 为积性函数，用线性筛可以筛出来，记得出循环的时候处理 mu[i * pr[j]] = 0 即可。事实上，所有积性函数都可以用线性筛筛出来，具体后面有提及。当然，还有更快的筛法。

2 莫比乌斯反演

接下来是重头戏。回顾一下前言中所提到的函数。不妨设

f(n) = \sum_{d \mid n} g(d)

那么，根据莫比乌斯反演，我们有

\boxed{ g(n) = \sum_{d \mid n} \mu(d) f(\frac nd) }

考虑证明。首先你可以用狄利克雷卷积爆杀，具体请参见相关的笔记。这里考虑另一种比较笨的证明方法：

\sum_{d \mid n} \mu(d) f(\frac nd) = \sum_{d\mid n} \mu(d) \sum_{d'\mid(n / d)} g(d')

到这里我们要理解一个常用的技巧：交换求和顺序。即，交换求和符号达到简化运算的目的。有的时候，交换求和顺序会导致一些值缺失或增加，要把它们给补上，本质上就是要让里面的每一项的值的和等价。

上面的式子中，不难发现 d 与 d' 枚举的范围都是在 n 中，一个枚举另一个剩下的。二者等价，因此直接交换求和顺序不会有什么影响。

即上述式子变为

\sum_{d'\mid n} g(d') \sum_{d\mid(n / d')} \mu(d)

根据上面我们得到的“至关重要的性质”，我们将式子变成

\sum_{d'\mid n} g(d') [\dfrac n{d'} = 1]

发现只有 d' = n 的时候才能满足上述条件，所以原式就是 g(n)。证毕。

除此之外，莫比乌斯反演还有另一种形式，令

f(n) = \sum_{n \mid d} g(d)

那么

\boxed{ g(n) = \sum_{n \mid d} \mu(\dfrac dn)f(d) }

证明是类似的。

同时我们尝试用莫反来理解一下上面的那个式子。

令 g(n) = [n = 1]，f(n) 为定义。

那么有

g(n) = \sum_{d \mid n} \mu(d) f(\dfrac nd) = \sum_{d \mid n} \mu(d) \sum_{d' \mid (n/d)} g(d')

令 n = \gcd(i,j)，那么有

g(\gcd(i,j)) = \sum_{d \mid \gcd(i,j)} \mu(d) \sum_{d' \mid (\gcd(i,j) / d)} g(d')

发现后面那个部分只有 d' = 1 的时候才有实际值，所以最后一项等于 1。最后得到的就是

[\gcd(i,j) = 1] = \sum_{d \mid \gcd(i,j)} \mu(d)

而且我们可以随便乱换变量得到

[x = 1] = \sum_{d \mid x} \mu(d)

需要注意的是，上面的式子用的其实并不多。更多的技巧会在下面题目说明。而且其实上面式子也可以相当灵活。只要记住 f = g * 1 \Leftrightarrow g = f * \mu 即可。具体参见狄利克雷卷积部分。

3 一些基础例题

前几道题目可以跟着题解走，后面就要试试自己推导了。

3.1 P2522 [HAOI2011] Problem b

题目就是求

\sum_{i = x}^n \sum_{j = y}^m [\gcd(i,j) = k]

的值。

首先先用简单的类似二维前缀和的方法优化式子，

\sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = k]

再去掉一个 k：

\sum_{i = 1}^{\lfloor n / k \rfloor} \sum_{j = 1}^{\lfloor m / k \rfloor} [\gcd(i,j) = 1]

用小性质优化一下：

\sum_{i = 1}^{\lfloor n / k \rfloor} \sum_{j = 1}^{\lfloor m / k \rfloor} \sum_{d \mid \gcd(i,j)} \mu(d)

接下来交换求和顺序，先枚举 d。

注意到这次的交换求和顺序不太一样，不能直接暴力交换。思考一下，在上述式子中，如果 d 要被枚举到，需要满足什么条件呢？当且仅当 d \mid i 并且 d \mid j，这是显然的。所以把这个部分计入到贡献当中。

\sum_{d} \mu(d) \sum_{i = 1}^{\lfloor n / k \rfloor} [d \mid i] \sum_{j = 1}^{\lfloor m / k \rfloor} [d \mid j]

后面两个式子你还不会化简？简单除法即可。

\sum_{d} \mu(d) \left\lfloor \frac{n}{dk} \right\rfloor \left\lfloor \frac{m}{dk} \right\rfloor 此时计算的时间复杂度是 $\mathcal O(n)$，但由于本题多组数据，目前还不能通过。发现我们可以做**整除分块**。具体的，我们将 $\left\lfloor \dfrac{n}{k} \right\rfloor, \left\lfloor \dfrac{m}{k} \right\rfloor$ 相等的一起算。做一手 $\mu(d)$ 的前缀和就可以 $\mathcal O(\sqrt n)$ 求答案了。现在可以通过本题了。 这是特别经典的套路了。 ### 3.2 P2257 YY的GCD 求 $$ \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) \in P] $$ 其中 $P$ 为质数集合。多组询问。 按照上面的题先套路的枚举质数，拆开来： $$ \sum_{k \in P} \sum_{d} \mu(d) \left\lfloor \frac{n}{dk} \right\rfloor \left\lfloor \frac{m}{dk} \right\rfloor $$ 发现这个时间复杂度过不了。 观察到仍然有多个求和，**交换一下求和符号试试**？当然我们不能直接交换，观察到内侧有两项和 $dk$ 均有关，不妨枚举 $dk$ 来做，令 $T = dk$，刚好是连续的。接下来，我们来交换符号，**先枚举 $T$。**先把后面的那个部分写下来。再考虑会有多少的 $\mu()$ 会加在这个部分上。我们要让求的和的值等价**不变**，由于 $d = \dfrac Tk$，据此写出： $$ \sum_{T = 1}^{\min(n,m)} \left\lfloor \frac{n}{T} \right\rfloor \left\lfloor \frac{m}{T} \right\rfloor \sum_{k \mid T, k \in P} \mu(\frac Tk) $$ 发现后面那个部分跟 $n,m$ 没有一点关系了。所以这个求和被我们优化掉了。开个数组记录一下就可以了。 注意，交换求和的意义是将东西一起计算，我们通常都会把一些相同的东西给组合到一起，这样就可以离线处理一些东西，继而达到降低时间复杂度的意义。 本质上是对结论的二次加工。下次做题先按照结论写出来先再推式子。 ### 3.3 P3312 [SDOI2014] 数表 先来学习一个数论函数。 > 约数和函数，定义为 > $$ > \sigma_x(n) := \sum_{d \mid n} d^x > $$ > 常将 $\sigma_1(n)$ 简写为 $\sigma(n)$。$\sigma(n)$ 是一个积性函数，可以用筛法筛出来。证明可以从定义出发简单说明。 先不考虑 $a$ 的限制。考虑求 $$ \sum_{i = 1}^n \sum_{j = 1}^m \sigma(\gcd(i,j)) $$ 发现后面这个东西很难搞，根据我们之前的经验： 1. 想办法把 $\gcd$ 取出来； 2. 先尝试额外枚举一些东西来达到我们的目的。 于是非常经典，来枚举一手 $d = \gcd(i,j)$ 的值。 $$ \sum_{d = 1}^{\min(n,m)} \sum_{i = 1}^{n} \sum_{j = 1}^{m} \sigma(d) [\gcd(i, j) = d] $$ 看到熟悉的式子，接下来就是按照套路拆。 $$ \sum_{d = 1}^{\min(n,m)} \sum_{i = 1}^{\left\lfloor n/d \right\rfloor} \sum_{j = 1}^{\left\lfloor m/d \right\rfloor} \sigma(d) [\gcd(i, j) = 1] $$ 把无关项往前提一下， $$ \sum_{d = 1}^{\min(n,m)} \sigma(d) \sum_{i = 1}^{\left\lfloor n/d \right\rfloor} \sum_{j = 1}^{\left\lfloor m/d \right\rfloor} [\gcd(i, j) = 1] $$ 直接把后面熟悉的式子暴拆一手， $$ \sum_{d = 1}^{\min(n,m)} \sigma(d) \sum_{k = 1}^{\min(\left\lfloor n/d \right\rfloor, \left\lfloor m/d \right\rfloor)} \mu(k) \left\lfloor \frac n{dk} \right\rfloor \left\lfloor \frac m{dk} \right\rfloor $$ 后面的式子跟上面一题类似，不妨令 $T = dk$，枚举 $T$： $$ \sum_{T = 1}^{\min(n,m)} \left\lfloor \frac nT \right\rfloor \left\lfloor \frac mT \right\rfloor \sum_{d \mid T} \sigma(d) \mu(\frac Td) $$ 由于 $\sigma(d)$ 是积性函数，一样的可以筛出来，一样的预处理后面的那个式子。像上一题一样，就做完了。 具体的，我们引入积性函数四步筛法： > 1. $x = 1$ 的时候，$f(x)$ 的值是多少？ > 2. $x = p$ 的时候，$f(x)$ 的值是多少？ > 3. $p \mid i$ 的时候，$f(ip)$ 的值是多少？ > 4. $p \nmid i$ 的时候，$f(ip)$ 的值是多少？ 然后我们套用欧拉筛的模板即可。 对于 $\sigma$ 函数，我们知道， 1. $\sigma(1) = 1$； 2. $\sigma(p) = p + 1$； 3. $\sigma(ip) = \sigma(i) \times (p + 1), p \nmid i$； 而对于 $p \mid i$ 的情况我们要多做一点分类讨论。 首先如果 $i = p^k$，由定义我们知道 $\sigma(ip) = \sigma(i) \times p + 1$。 发现其他地方并不好筛，引入新的函数 $g(x)$， 表示 $x$ 的最小质因子的幂，就是 $p^x$ 啦，否则根据线性筛流程，我在枚举前面的质数时候就肯定出现了 $p' \mid i$ 的情况了。 那么我们就提出所有的 $p$，记剩下的部分为 $R$，因数和显然就是选择一个次幂，然后再选择一个剩下 $R$ 的因数，讲所有的情况加起来，即 $\sigma (R) \times \sigma(p \times g(i))$。 所以最后就有 $\sigma(ip) = \sigma(\dfrac i{g(i)}) \times \sigma(p \times g(i))$。 接下来分析 $g(x)$ 这个函数。 1. $g(1) = 1$； 2. $g(p) = p$； 3. $g(ip) = p, p \nmid i$； 4. $g(ip) = g(i) \times p, p \mid i$。 接着套用线性筛的流程，我们就可以把 $g(x), \mu(x), \sigma(x)$ 全部一次性的筛出来了。那么上面那个式子就很好办了。 但是这题有 $a$ 的限制！怎么做呢？ 由于后面的式子跟 $n,m$ 无关，所以不妨先给询问从小到大排序，然后从小到大去枚举 $a$。不妨令 $h(T) = \sum_{d \mid T} \sigma(d) \mu(\frac Td)$，那么原式就变成了 $$ \sum_{T = 1}^{\min(n,m)} \left\lfloor \frac nT \right\rfloor \left\lfloor \frac mT \right\rfloor h(T) $$ 考虑 $a$ 的变化会带来什么贡献，显然的，当 $\sigma(d) \leq a$ 的时候才会带来贡献。而 $a$ 的变化势必会对一些 $h(T)$ 造成影响。由于 $T$ 是跟 $d$ 有关系的，所以我们只需要枚举 $d$，然后枚举倍数即可。 先记录好每一个 $\sigma(d)$ 对应的 $d$，然后排序一手。每次 $a$ 变化的时候把变化的部分的 $\sigma(d)$ 拿上来，更改 $h()$ 的对应的值。发现我们最后在做整除分块的时候还要求和，所以为了时间复杂度，我们这个部分不能使用前缀和，而是使用树状数组。 然后发现这题就做完了，求答案是 $\mathcal O(q \log n \sqrt n)$，更改答案是 $\mathcal O(n \ln n \log n) = \mathcal O(n \log^2 n)$。 挺难的题目。 ### 3.4 P3327 [SDOI2015] 约数个数和 如果知道这是一道莫比乌斯反演的题目，那么首先我们要找到 $\gcd$。 考虑下面这个式子。你不知道就做不出来了。 $$ d(ij) = \sum_{x \mid i} \sum_{y \mid j} [\gcd(x,y) = 1] $$ 证明如下： > 不妨令 $ij$ 的某个约数 $k$ 有一个因子 $p^c$，而 $i$ 中有 $p^a$，$j$ 中有 $p^b$。规定： > > - 若 $c \leq a$，那么因子全部都在 $i$ 中选取。 > - 若 $c > a$，那么选择 $p^a$ 之后，再在 $j$ 中选取 $p^{c-a}$。 > > 容易发现这么选择可以使得因子数量不重不漏。 > > 发现 $x \mid i$ 与 $y \mid j$ 本质上是在枚举 $i,j$ 的因子。 > > 那么考虑 $x,y$ 放一起的时候怎样才能计入答案。发现对于第一个部分，相当于只在 $x$ 中选取 $p$。而对于第二个部分，由于 $p^a$ 是固定要求取的，相当于**只在** $y$ 中选取 $p$。 > > 这个和要求 $[\gcd(x,y) = 1]$ 是一致的。证毕。 所以我们现在要求的式子变成了： $$ \sum_{i = 1}^n \sum_{j = 1}^m \sum_{x \mid i} \sum_{y \mid j} [\gcd(x, y) = 1] $$ 先利用性质把后面的判别式拆开： $$ \sum_{i = 1}^n \sum_{j = 1}^m \sum_{x \mid i} \sum_{y \mid j} \sum_{d \mid \gcd(x,y)} \mu(d) $$ 好多 $\sum$ 啊。来一个个拆掉。发现第三个和第四个 $\sum$ 不再是我们熟悉的从 $1$ 到一个上界了，所以这题的处理稍微有点不同。仍然还是很套路的枚举一手 $d$ 的值。 $$ \sum_{i = 1}^n \sum_{j = 1}^m \sum_{x \mid i} \sum_{y \mid j} \sum_{d = 1}^{\min(n,m)} \mu(d) \times [d \mid \gcd(x,y)] $$ 这两个显然等价。但是现在第五个 $\sum$ 摆脱了 $x,y$ 的限制，可以直接交换求和顺序了。 $$ \sum_{d = 1}^{\min(n,m)} \mu(d) \color{red}{\sum_{i = 1}^n \sum_{j = 1}^m \sum_{x \mid i} \sum_{y \mid j} [d \mid \gcd(x,y)]} $$ 现在专注于红色的部分。首先，常用套路是交换求和顺序。这是其中一个常用的求和交换： $$ \begin{aligned} {\color{red} \text{Red Part}} =& \sum_{x = 1}^n \sum_{y = 1}^m\sum_{i=1}^n [x \mid i] \sum_{j=1}^m [y \mid j][d \mid \gcd(x,y)] \\ =& \sum_{x = 1}^n \sum_{y = 1}^m \left\lfloor\dfrac nx\right\rfloor \left\lfloor\dfrac my\right\rfloor [d \mid \gcd(x,y)] \end{aligned} $$ 继续尝试化简。感觉 $[d\mid \gcd(x,y)]$ 这个条件太烦了。通过改变枚举方式优化掉。 $$ \sum_{x = 1}^{\lfloor n/d \rfloor} \sum_{y = 1}^{\lfloor m/d \rfloor} \left\lfloor\dfrac n{dx}\right\rfloor \left\lfloor\dfrac m{dy}\right\rfloor $$ 发现第一项跟 $y$ 没有关系，赶紧拉出来。 $$ (\sum_{x = 1}^{\lfloor n/d \rfloor} \left\lfloor\dfrac n{dx}\right\rfloor) (\sum_{y = 1}^{\lfloor m/d \rfloor} \left\lfloor\dfrac m{dy}\right\rfloor) $$ 发现这个东西其实是可以变成 $$ (\sum_{x = 1}^{\lfloor n/d \rfloor} \left\lfloor\dfrac {\lfloor n / d \rfloor}{x} \right\rfloor) (\sum_{y = 1}^{\lfloor m/d \rfloor} \left\lfloor\dfrac {\lfloor m / d \rfloor}{y}\right\rfloor) $$ 所以先处理出 $\sum \limits _{x = 1}^{s} \left\lfloor s/x \right\rfloor$ 这个东西，显然可以整除分块，设得到的值为 $F(s)$。 最后带回原式就是： $$ \sum_{d=1}^{\min(n,m)}\mu(d) F(\left\lfloor\dfrac nd \right\rfloor) F(\left\lfloor\dfrac md \right\rfloor) $$ 这个明显可以用整除分块求。所以最后的时间复杂度就是 $\mathcal O((T + n) \sqrt n)$。可以通过本题。 --- 然而这题还可以单纯使用莫反来解决问题，其本质也是一样的。这里也演示一下。 对于式子 $$ \sum_{i = 1}^n \sum_{j = 1}^m \sum_{x \mid i} \sum_{y \mid j} [\gcd(x,y) = 1] $$ 我们先按照上面的相同套路把式子化成 $$ \sum_{x = 1}^n \sum_{y = 1}^m \left\lfloor\dfrac nx\right\rfloor \left\lfloor\dfrac my\right\rfloor [\gcd(x,y) = 1] $$ 然后开始莫比乌斯反演。我们令 $$ g(x) = \sum_{i = 1}^n \sum_{j = 1}^m \left\lfloor\dfrac ni\right\rfloor \left\lfloor\dfrac mj\right\rfloor [\gcd(i,j) = x] \\ f(x) = \sum_{x \mid d} g(d) $$ 那么其实 $$ f(x) = \sum_{i = 1}^n \sum_{j = 1}^m \left\lfloor\dfrac ni\right\rfloor \left\lfloor\dfrac mj\right\rfloor [x \mid \gcd(i,j)] $$ 这一步和第一种做法一致。都是改变枚举方式，消除 $[x \mid \gcd(i,j)]$： $$ f(x) = \sum_{i = 1}^{\lfloor n / x \rfloor} \sum_{j = 1}^{\lfloor m / x \rfloor} \left\lfloor\dfrac {n}{xi}\right\rfloor \left\lfloor\dfrac m{xj}\right\rfloor $$ 接下来根据莫比乌斯反演，就有： $$ g(x) = \sum_{x \mid d} \mu(\dfrac dx) f(d) = \sum_{x \mid d} \mu(\dfrac dx) \sum_{i = 1}^{\lfloor n / d \rfloor} \sum_{j = 1}^{\lfloor m / d \rfloor} \left\lfloor\dfrac {n}{di}\right\rfloor \left\lfloor\dfrac m{dj}\right\rfloor $$ 挺吓人，但是答案其实是 $g(1)$，不妨代进去看看。 $$ g(1) = \sum_{d} \mu(d) {\color{red} \sum_{i = 1}^{\lfloor n / d \rfloor} \sum_{j = 1}^{\lfloor m / d \rfloor} \left\lfloor\dfrac {n}{di}\right\rfloor \left\lfloor\dfrac m{dj}\right\rfloor} $$ 红色这个部分用上一个部分的做法一样的去做就行。 这种办法还要用莫反公式，我个人还是比较喜欢第一种，虽然本质相同。 ### 3.5 P1829 [国家集训队] Crash的数字表格 / JZPTAB 居然自己做出来了。有点上头。 但是做得还是挺慢的，不够熟练。 回到题目，我们要求 $$ \sum_{i = 1}^n \sum_{j = 1}^m \dfrac{ij}{\gcd(i,j)} $$ 先简单的枚举一下 $\gcd$ 的值。 $$ \sum_{d} \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = d] \dfrac {ij}d $$ 思考一下，$\dfrac {ij}d$ 这个式子的本质是什么？相当于把两个式子乘起来，然后把重复的部分给删掉一份。 我们还可以理解成：把两个式子重复的部分去掉，然后再乘上相同的一份。有了这个想法，把式子改写成： $$ \sum_{d} \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = d] \dfrac id \cdot \dfrac jd \cdot d $$ 好烦的 $d$，拉走。 $$ \sum_{d} d \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = d] \dfrac id \cdot \dfrac jd $$ 看到 $[\gcd(i,j) = d]$，很自然的想法是改变枚举项，变为枚举 $id$ 和 $jd$。 $$ \sum_{d} d \sum_{i = 1}^{\lfloor n / d\rfloor} \sum_{j = 1}^{\lfloor m/d \rfloor} [\gcd(i,j) = 1] ij $$ 发现这个式子变的非常优美，似乎有意无意地说明了我们目前为止是正确的。 这个时候可以很轻松的莫反了。接着爆拆这个式子。 $$ \begin{aligned} \sum_{d} d \sum_{i = 1}^{\lfloor n / d\rfloor} \sum_{j = 1}^{\lfloor m/d \rfloor} \sum_{d' \mid \gcd(i,j)} \mu(d') \cdot ij &= \sum_{d} d \sum_{d'} \mu(d') \sum_{i = 1}^{\lfloor n / d\rfloor} [d' \mid i] \sum_{j = 1}^{\lfloor m/d \rfloor} [d' \mid j] ij \\ &= \sum_{d} d \sum_{d'} \mu(d') {\left(\sum_{i = 1}^{\lfloor n / d\rfloor} [d' \mid i]i\right)} {\left(\sum_{j = 1}^{\lfloor m/d \rfloor} [d' \mid j]j\right)} \\ &= \sum_{d} d \sum_{d'} \mu(d') \cdot (d')^2 {\color{red} \left(\sum_{i = 1}^{\lfloor n / (dd')\rfloor} i\right)} {\color{blue}\left(\sum_{j = 1}^{\lfloor m/(dd') \rfloor} j\right)} \end{aligned} $$ 发现红色和蓝色的部分结构一致。不妨单独拿出来，令 $F(x) = \sum_{i = 1}^x i$。发现这个就是等差数列，可以 $\mathcal O(1)$。 原式子变为 $$ \sum_{d} d \sum_{d'}\mu(d') \cdot (d')^2 \cdot F(\dfrac {n}{dd'}) \cdot F(\dfrac m{dd'}) $$ 考虑 $d$ 为定值的时候，提前处理 $\mu(d') \cdot (d')^2$ 的前缀和，内部式子可以整除分块的去算。时间复杂度是 $\mathcal O(\sqrt n)$。 发现里面这个式子与外面这个式子的联系仅有 $\dfrac nd$ 和 $\dfrac md$。然后这个 $d$ 也可以用前缀和或者等差数列去优化。所以外部的时间复杂度也是 $\mathcal O(\sqrt n)$。所以总的时间复杂度是 $\mathcal O(n)$。 然后发现这题就可以过了。 ### 3.6 [AGC038C] LCMs / P3911 最小公倍数之和 求 $$ \sum_{i = 1}^n \sum_{j = 1}^n \operatorname{lcm}(A_i, A_j) $$ 首先看到这个 $A_i$ 就很流汗黄豆了。这个不好做啊！ 发现 $A_i$ 范围限定的比较死，不妨把 $n$ 设为值域大小，然后把 $A_i$ 丢到计数器里面。记为 $cnt$。 然后是常规套路，上面已经演示过多遍： $$ \begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n \operatorname{lcm}(i,j) \cdot cnt_i \cdot cnt_j &= \sum_{i = 1}^n \sum_{j = 1}^n \dfrac {ij}{\gcd(i,j)} \cdot cnt_i \cdot cnt_j \\ &= \sum_{d = 1}^n d \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i,j) = d] \dfrac id \cdot \dfrac jd \cdot cnt_i \cdot cnt_j \\ &= \sum_{x = 1}^n x \sum_{i = 1}^{\lfloor n / x \rfloor} \sum_{j = 1}^{\lfloor n / x \rfloor} \sum_{d \mid \gcd(i,j)} \mu(d) \cdot i \cdot j \cdot cnt_{ix} \cdot cnt_{jx} \\ &= \sum_{x = 1}^n x \sum_{d = 1}^{\lfloor n / x\rfloor} \mu(d) \cdot d^2 \cdot \left(\sum_{i = 1}^{\lfloor n / (dx) \rfloor} cnt_{idx} \cdot i\right)^2 \end{aligned} $$ 将后面那个记作 $S(dx)$。原式子变为 $$ \sum_{x = 1}^n x \sum_{d = 1}^{\lfloor n / x \rfloor} \mu(d) \cdot d^2 \cdot S^2(dx) $$ 这个 $dx$ 好烦，枚举 $T = dx$，套路的拆出来。 $$ \sum_{T = 1}^n S^2(T) \cdot T \sum_{d \mid T} \mu(d) \cdot d $$ 这个就可以 $\mathcal O(n \log n)$ 的算了。$S$ **暴力求**，第二个 $\sum$ 可以预处理。 别再惦记着你那整除分块了。能跑就跑，不要乱搞。 ### 3.7 P6222 「P6156 简单题」加强版 以一个综合性很强的题目来结束这一节。 >求 >$$ >\left(\sum_{i=1}^n \sum_{j = 1}^n \mu^2(\gcd(i,j)) \cdot \gcd(i,j) \cdot (i + j)^k\right) \bmod 2^{32} >$$ >$n \leq 10^7, 1 \leq k < 2^{31}$，多组数据，$T \leq 10^4$，$1.5\text s$。 恐怖的数据范围注定这题最多只能 $\mathcal O(n)$，最多带一个非常小的东西。 - 套路一：枚举 $\gcd$。 $$ \begin{aligned} \sum_{i=1}^n \sum_{j = 1}^n \mu^2(\gcd(i,j)) \cdot \gcd(i,j) \cdot (i + j)^k &= \sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i,j) = d](i + j)^k \cdot d \cdot \mu^2(d) \\ &= \sum_{d = 1}^n d \cdot \mu^2(d) \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i,j) = d](i + j)^k \\ \end{aligned} $$ - 套路二：改变枚举的对象，这里改 $i,j$ 为 $id, jd$。 $$ \begin{aligned} \sum_{d = 1}^n d \cdot \mu^2(d) \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i,j) = d](i + j)^k &= \sum_{d = 1}^n d^{k + 1} \cdot \mu^2(d) \sum_{i = 1}^{\lfloor n / d\rfloor} \sum_{j = 1}^{\lfloor n / d\rfloor} [\gcd(i,j) = 1](i + j)^k \end{aligned} $$ - 套路三：最经典的一个 $[\gcd(i,j) = 1] = \sum_{d \mid \gcd(i,j)} \mu(d)$，或者写作 $\varepsilon(\gcd(i,j)) = (\mu * \mathbf 1)(\gcd(i,j))$。 下面稍微换了一下变量名字。然后套路一二一起上。 $$ \begin{aligned} \sum_{x = 1}^n x^{k + 1} \cdot \mu^2(x) \sum_{i = 1}^{\lfloor n / x\rfloor} \sum_{j = 1}^{\lfloor n / x\rfloor} \sum_{d \mid \gcd(i, j)} \mu(d) \cdot (i + j)^k &= \sum_{x = 1}^n x^{k + 1} \cdot \mu^2(x) \sum_{d = 1}^{\lfloor n / x\rfloor} \mu(d) \sum_{i = 1}^{\lfloor n / x\rfloor} [d \mid i] \sum_{j = 1}^{\lfloor n / x\rfloor} [d \mid j] (i + j)^k \\ &= \sum_{x = 1}^n x^{k + 1} \cdot \mu^2(x) \sum_{d = 1}^{\lfloor n / x\rfloor} \mu(d) \cdot d^{k} {\color{red} \sum_{i = 1}^{\lfloor n / (dx)\rfloor}\sum_{j = 1}^{\lfloor n / (dx)\rfloor} (i + j)^k} \end{aligned} $$ 先稍微停停手，看看我们现在剩下的是什么。 首先看到上面的红色部分。发现这个部分跟外面貌似只跟 $dx$ 有关系。 - 套路四：预处理一些值。 考虑令 $S(x) := \sum_{i = 1}^x \sum_{j = 1}^x (i + j)^k$，怎么 $\mathcal O(n)$ 预处理 $x$ 呢。 观察到我们可以从 $S(x - 1)$ 预处理到 $S(x)$，研究一下这个增量是怎么求的。 发现多出来的无非是形如 $(i + x)^k$ 类型的式子。具体的，多的部分是 $2(\sum_{i = 1}^x (i + x)^k) - (2x)^k$。 这就是一堆自然数幂和。自然数幂和可以用筛法求出。 然后我们就可以在近 $\mathcal O(n)$ 的时间复杂度里面预处理这个东西。 所以原来的式子就变成了 $$ \sum_{x = 1}^n x^{k + 1} \cdot \mu^2(x) \sum_{d = 1}^{\lfloor n / x\rfloor} \mu(d) \cdot d^{k} \cdot S(\lfloor \dfrac{n}{dx} \rfloor) $$ - 套路五：令 $T = dx$。 一个相当常用的套路。在拆式子进行到后半部分的时候，当出现诸如 $dx$ 之类的式子，可以尝试进行这样的拆解。 于是就有 $$ \sum_{T = 1}^n T^k \cdot S(\left \lfloor \dfrac{n}{T} \right \rfloor) {\color{green} \sum_{x \mid T} \mu^2(x) \cdot x \cdot \mu(\dfrac{T}{x})} $$ 然后就是预处理环节了。 首先次幂是可以使用筛法和快速幂做到近 $\mathcal O(n)$ 预处理的，实际上会带一个没太大关系的 $\log$。 $S$ 我们讨论过了。 考虑绿色部分的式子。非常像狄利克雷卷积啊！ 我们知道 $\mu, \mu^2, \textrm {id}$ 都是积性函数，再根据狄利克雷卷积的性质，所以这一个东西应该也是积性函数才对。 - 套路六：通过积性函数四步筛法处理出我们想要的东西。 回顾一下这个在前面出现的套路： > 1. $x = 1$ 的时候，$f(x)$ 的值是多少？ > 2. $x = p$ 的时候，$f(x)$ 的值是多少？ > 3. $p \mid i$ 的时候，$f(ip)$ 的值是多少？ > 4. $p \nmid i$ 的时候，$f(ip)$ 的值是多少？ 不妨令 $h(x) = \sum_{d \mid x} \mu^2(d) \cdot \mu(\dfrac xd) \cdot d$。 首先，$h(1) = 1$，根据积性函数，我们知道当 $p \nmid i$ 的时候，$h(ip) = h(i) \cdot h(p)$。 而 $h(p)$ 由于只有两个因子，带入即可知道 $h(p) = \mu^2(p) \cdot \mu(1) \cdot p + \mu^2(1) \cdot \mu(p) \cdot 1 = p - 1$。 然后来重点看 $p \mid i$ 的情况，根据以往的经验，我们还要额外再处理一些东西，记录质因数分解最大的那个质数 $p$ 的次数 $k$。 以下的 $k$ 是从 $ip$ 那里算出来的，最大的那个质数是 $p$。 $k = 0,1$ 的情况即为 $h(1), p \nmid i$，已经讨论过了。 $k = 2$ 的时候，虽然 $p \mid i$，但由于 $p^2 \nmid i$，按照同样的方法，可以代入得到 $h(p^2) = -p$，再与 $h(i)$ 乘起来即可。 然后 $k = 3$ 就有点尴尬了，代入发现结果是 $0$。由于 $p^3 \mid ip$，那么，$\mu(d)$ 和 $\mu(\dfrac {ip}d)$，你总得有一个会被 $p^2$ 整除，那么式子答案就是 $0$ 了。 $k > 3$ 也一样。 再考虑 $k$ 怎么求。首先我们发现每次线筛枚举到的 $p$ 一定是 $ip$ 的最大的质因子，否则 $i$ 就已经被跳出循环了。 然后我们只需要考虑这两个问题：$p \mid i$ 吗？$p^2 \mid i$ 吗？因为我们不关心 $k \geq 3$ 之后具体值是多少。 所以 $k$ 只需要简单的 `if`，不需要额外去筛 $k$。 然后算答案用整除分块。 最终时间复杂度近似于 $\Theta(n + T\sqrt{n})$。 ## 4 狄利克雷卷积与杜教筛 请参见狄利克雷卷积和杜教筛的单独文章。 下面来点题目。不过好像也不是很多。 ### 4.1 P3768 简单的数学题 $$ \sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j) \times ij $$ 先按照 3.5 的套路去拆解这个式子。 $$ \begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j) \times ij &= \sum_{d = 1}^n d \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i,j) = d] \times ij \\ &= \sum_{d = 1}^n d^3 \sum_{i = 1}^{\lfloor n / d\rfloor} \sum_{j = 1}^{\lfloor n / d \rfloor} [\gcd(i,j) = 1] \times ij \\ &= \sum_{d = 1}^n d^3 \sum_{i = 1}^{\lfloor n / d\rfloor} \sum_{j = 1}^{\lfloor n / d\rfloor} \sum_{d' \mid \gcd(i,j)} \mu(d') \times ij \\ &= \sum_{d = 1}^n d^3 \sum_{d' = 1}^{\lfloor n / d\rfloor} \mu(d') \cdot (d')^2 \sum_{i = 1}^{\lfloor n / (dd')\rfloor} \sum_{j = 1}^{\lfloor n / (dd')\rfloor} ij \end{aligned} $$ 令 $sum(i) := \sum_{i = 1}^n i$，原式变为： $$ \sum_{d = 1}^n d^3 \sum_{d'=1}^{\lfloor n / d\rfloor} \mu(d') \cdot (d')^2 \cdot \left(sum(\lfloor \dfrac n{dd'} \rfloor)\right)^2 $$ 里面那个东西好无语啊。不妨沿用经典套路，设 $T = dd'$，然后交换求和顺序，把里面那个东西拉出来 $$ \sum_{T = 1}^{n} \left(sum(\lfloor \dfrac nT \rfloor)\right)^2 \sum_{d \mid T} d^3 \cdot \dfrac {T^2}{d^2} \cdot \mu(\dfrac Td) $$ 然后约分，拉出来 $$ \sum_{T = 1}^{n} \left(sum(\lfloor \dfrac nT \rfloor)\right)^2 \cdot T^2 \sum_{d \mid T} d \cdot \mu(\dfrac Td) $$ 后面那个东西不就是 $\mathrm{id} * \mu = \varphi$ 吗，哎呦，抬走了 $$ \sum_{T = 1}^{n} \left(sum(\lfloor \dfrac nT \rfloor)\right)^2 \cdot T^2 \cdot \varphi(T) $$ 接下来令 $f(x) := x^2 \cdot \varphi(x)$，那么原式子其实可以 $\mathcal O(\sqrt n)$ 的去算了。问题现在聚焦在如何快速求出 $f(x)$ 上面了，这个猜测可以用杜教筛。 令 $S(x) := \sum_{i = 1}^x f(i)$ 不妨设 $g(x)$ 使得我们能够快速求出 $S(n)$。 先把式子带进去看看。我们要快速求出 $$ \sum_{i = 1}^n (f * g)(i) = \sum_{i = 1}^n \sum_{d \mid i} f(d) g(\dfrac nd) = \sum_{i = 1}^n \sum_{d \mid i} d^2 \cdot \varphi (d) \cdot g(\dfrac id) $$ 发现 $d^2$ 太烦了。而且根据之前我们在杜教筛中提到的筛 $\varphi(i) \cdot i$ 的经验，我们令 $g(x) := x^2$。 那么原式子变成 $$ \sum_{i = 1}^n \sum_{d \mid i} i^2 \varphi (d) = \sum_{i = 1}^n i^2 \sum_{d \mid i} \varphi (d) $$ 拯救我吧，$\varphi * \mathbf 1 = \mathrm{id}$！ $$ \sum_{i = 1}^n i^3 = \begin{pmatrix} n + 1 \\ 2 \end{pmatrix}^2 $$ 现在这个式子变成小丑了。 那么我们就可以在总计 $\mathcal O(n^{2/3})$ 的时间复杂度内用杜教筛求出需要的值，在 $\mathcal O(n^{1/2})$ 的时间复杂度内用整除分块计算答案。总时间复杂度是 $\mathcal O(n^{2/3})$。足以通过本题。 ## 5 初探 prod 你说得对，但是有的时候会出现比较阴间的 $\prod$ 来恶心你。 虽然本质上的逻辑是和 $\sum$ 差不多，但是还是来专门写一下，直接看题吧。 ### 5.1 P5221 Product > 求 > $$ > \left(\prod_{i = 1}^n \prod_{j= 1}^n \dfrac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\right) \bmod 104857601 > $$ > $n \leq 10^6,0.2\text s, 7.81 \text{MB}$。 首先 cyj 非常凶残的卡时间。而且不知道出于什么目的把空间卡的非常死。 不管了，我们先拆爆这个式子先。 $$ \begin{aligned} \prod_{i = 1}^n \prod_{j = 1}^n \dfrac{\operatorname{lcm}(i,j)}{\gcd(i,j)} &= \prod_{i = 1}^n \prod_{j = 1}^n \dfrac {ij}{(\gcd(i,j))^2} \end{aligned} $$ 上面的那个部分其实是好算的，是 $(n!)^{2n}$，那么我们现在的问题就是要求 $$ \prod_{i = 1}^n \prod_{j = 1}^n (\gcd(i,j))^2 $$ 先把碍事的平方叉掉。 基本套路还是一样的，枚举 $\gcd$ 的值。但是，这次不是简单的相加了，我们要考虑一下这么交换顺序有什么用。 每一次出现 $\gcd(i,j) = d$ 的时候，最后式子就会乘上 $d$，所以这个反演出现在了**指数**的位置，比较独特。（这里为了观感使用 `\normalsize` 放大了指数部分，以后所有 `\prod` 相关的指数都会放大） $$ \prod_{d = 1}^n d^{\normalsize \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i,j) = d]} $$ 单把指数拿出来看，按照套路爆拆，如果不懂的建议重修第一道例题。 $$ \sum_{x = 1}^{\lfloor n / d \rfloor} \mu(x) \left(\left\lfloor \dfrac n{dx} \right\rfloor\right)^2 $$ 注意，根据费马小定理，在对指数做操作的时候，要对模数减一取模。 里面这个式子可以 $\mathcal O(\sqrt n)$ 的整除分块，这个值跟 $\left\lfloor \dfrac nd\right\rfloor$ 有关。然后你发现外面这个东西也可以整除分块。 所以总的时间复杂度是 $\mathcal O(n)$。 题目还可以，但是要对空间进行优化，不能开额外的数组。shaber 出题人。鉴定为玩《明日方舟》玩的。 本题也存在简单的使用 $\varphi$ 的 $\mathcal O(n)$ 做法。显然就是对那个指数下手。 ### 5.2 P3704 [SDOI2017] 数字表格 这是一道时间复杂度分析题目。 > 求 > $$ > \left(\prod_{i = 1}^n \prod_{j = 1}^m f_{\gcd(i,j)}\right) \bmod (10^9 + 7) > $$ > 我们定义 $f$ 为**斐波那契数列**，其中 $f(0) = 0, f(1) = 1$。 > > 多组数据，$T \leq 10^3$，$n,m \leq 10^6$。 按照上面题目的思路，我们还是套路的拆开，先枚举 $\gcd$，原式变为 $$ \prod_{d = 1}^{\min(n,m)} f_d ^{\normalsize \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = d]} $$ 关注指数部分，仍然还是要记得，指数是对模数减一取模。 显然指数可以拆成 $$ \sum_{x = 1}^{\min(\lfloor n / d \rfloor, \lfloor m / d \rfloor)} \mu(x) \left\lfloor \dfrac{n}{dx} \right\rfloor \left\lfloor \dfrac{m}{dx} \right\rfloor $$ 那么原式子就是 $$ \prod_{d = 1}^{\min(n,m)} f_d ^{\normalsize \sum_{x = 1}^{\min(\lfloor n / d \rfloor, \lfloor m / d \rfloor)} \mu(x) \lfloor n / (dx) \rfloor \lfloor m / (dx) \rfloor} $$ 发现外面可以整除分块，里面可以整除分块，还有一个调和级数，直接做的话，时间复杂度是 $$ \mathcal O(T \log M \cdot \int_{0}^{\sqrt n} \sqrt{\dfrac nx} \textrm dx + n \log M) = \mathcal O(T \cdot \log M \cdot n^{3/4} + n \log M) $$ 其中 $M$ 为模数。 大概是过不了的。本地三秒钟，洛谷炸成 60，但是 LOJ 过了，挺厉害。 发现这个式子很难优化，但是观察到有 $dx$。能不能沿用我们之前学过的枚举 $T = dx$ 的技巧？这其实是一个很常用的优化，试一试。 首先先把 $\prod_{T = 1}^{\min(n, m)}$ 给摆出来。观察到 $f_d$ 为唯一的底数，所以再把 $\prod_{d \mid T}$ 写下来。然后指数照抄。 $$ \prod_{T = 1}^{\min(n, m)} \prod_{d \mid T} f_{d}^{\normalsize \mu(\dfrac Td) \lfloor n / T \rfloor \lfloor m / T \rfloor} $$ 提取公共部分。 $$ \prod_{T = 1}^{\min(n, m)} \left(\prod_{d \mid T} f_{d}^{\normalsize \mu(\dfrac Td)}\right)^{\normalsize \lfloor n / T \rfloor \lfloor m / T \rfloor} $$ 观察到里面的那个式子是可以在 $\mathcal O(n \ln n \log M)$ 的时间复杂度内预处理的。所以这个式子被优化掉了。记作 $S(T)$。 改写为 $$ \prod_{T = 1}^{\min(n, m)} S(T)^{\normalsize \lfloor n / T \rfloor \lfloor m / T \rfloor} $$ 记录前缀积及其逆元，然后这个可以整除分块，单次在 $\mathcal O(\sqrt n \cdot \log M)$ 的时间复杂度拿下，总时间复杂度 $\mathcal O(n \ln n \log M + T \sqrt n \cdot \log M)$。 但是还有一个小优化，预处理可以做到 $\mathcal O(n (\ln n + \log M))$。具体的，发现 $\mu$ 只有 $0, 1, -1$，这个可以提前算出来。然后再跑就行了，这样就可以快一点。 最终时间复杂度 $\mathcal O(n (\ln n + \log M) + T \sqrt n \cdot \log M)$。这就是某省队队长口中的特别好玩的题目。 #### 5.2.1 扩展 现在假设我们要支持修改。 具体的，我们把 $T$ 次询问删除，换为如下操作： - 选择区间 $[l, r]$，将其中的 $f$ 分别乘上 $u$，并将答案输出。 我们应该怎么做？ 可能会想到用 ds 去做，但是对于这个问题我们还不需要。 我们并不需要去维护 $f$，我们只要答案。注意到修改之后对答案的贡献显然是形如 $u$ 的若干次方。 $$ \prod_{d = 1}^{\min(n,m)} f_d ^{\normalsize \sum_{x = 1}^{\min(\lfloor n / d \rfloor, \lfloor m / d \rfloor)} \mu(x) \lfloor n / (dx) \rfloor \lfloor m / (dx) \rfloor} $$ 看到这个式子我们发现，可以尝试去使用前缀和去计算这个指数。 具体的，我们先枚举 $d$ 再枚举 $x$，显然这个指数的和是可以在 $O(n \ln n)$ 的时间复杂度里面计算出来的。 由于这个东西可以预处理。那么这不就是大水题了。 记得指数模数为 $-1$。 ## 6 更加 Intensive 的技巧 基本按照 zak 的课件一步一步学的。 ### 6.1 简单莫反题目通用方法 首先先做一点复习训练。观察到之前的很多题目都可以被总结为下面的这个题目： > 给定 $A,B,C$，求 > $$ > \sum_{i = 1}^n \sum_{j = 1}^n A(i)B(j)C(\gcd(i,j)) > $$ > $n \leq 10^6$。多组数据。 之前已经在 3.7 节详细列举过各种这类基础题目的技巧。所以这里不展开讲了。 枚举 $\gcd$ 得到： $$ \sum_{k = 1}^n \sum_{i = 1}^n \sum_{j = 1}^n A(i)B(j)C(k)[\gcd(i,j) = k] $$ 令 $i \leftarrow ik, j \leftarrow jk$。 $$ \sum_{k = 1}^n C(k)\sum_{i = 1}^{\lfloor n / k \rfloor} \sum_{j = 1}^{\lfloor n / k \rfloor} A(ik)B(jk) [\gcd(i,j) = 1] $$ 反演。 $$ \sum_{k = 1}^n C(k)\sum_{i = 1}^{\lfloor n / k \rfloor} \sum_{j = 1}^{\lfloor n / k \rfloor} A(ik)B(jk) \sum_{d \mid \gcd(i, j)} \mu(d) $$ 换位置。 $$ \sum_{k = 1}^n C(k) \sum_{d = 1}^{\lfloor n/k \rfloor} \mu(d) \sum_{i = 1}^{\lfloor n / dk \rfloor} A(idk) \sum_{j = 1}^{\lfloor n / dk \rfloor} B(jdk) $$ 令 $T = dk$。 $$ \sum_{T = 1}^n \left(\sum_{i = 1}^{\lfloor n / T \rfloor} A(iT) \right) \left(\sum_{j = 1}^{\lfloor n / T \rfloor} B(jT) \right) \left(\sum_{k \mid T} C(k) \mu(\dfrac Tk) \right) $$ 这三项都只跟 $T$ 有关，且都可以在 $\mathcal O(n \log n)$ 的时间复杂度内预处理。这就是这类问题的通用解法。 之后整除分块计算即可。 ### 6.2 $S(ij)$ 通用方法 > 给定 $n, m$，求 > $$ > \sum_{i = 1}^n \sum_{j = 1}^m S(ij) > $$ > 其中 $S(ij)$ 是一个积性函数。$n, m \leq 5 \times 10^5$。 > > 举例为 P8570。 与上面的问题相比，这个问题相对困难一些。 由于积性函数是与互质有关的，不妨还是枚举 $k = \gcd(i, j)$。 $$ \sum_{k = 1}^{\min(n,m)} \sum_{i = 1}^{\lfloor n / k \rfloor} \sum_{j = 1}^{\lfloor m / k \rfloor} S(ijk^2) [\gcd(i,j) = 1] $$ 观察到出现了 $[\gcd(i,j) = 1]$ 的条件，那么如果要统计进答案，$i,j$ 必须互质，这为我们接下来的工作提供了很多便利。 此时如果 $k = 1$，那么 $S(ijk^2) = S(ij) = S(i)S(j)$，问题就变得非常可做，套用 6.1 的方法就可以快速解决。 考虑 $k > 1$ 的情况。我们能不能找到一个函数，使得也能像上面那样掰成两个部分去做呢？其实是可以的。 不妨令 $H(i) = \dfrac {S(k^2i)}{S(k^2)}$。观察到这个函数有一些帮助拆式子的性质。 首先我们来说明 $H(i)$ 是一个积性函数。感谢 `zhy_learn` 提供的方法。 我们知道 $i,j$ 互质，但我们并不知道 $i$ 与 $k^2$ 是否互质。 不妨把 $k^2$ 划分为三个部分 $w_1, w_2, w_3$，其中 $w_1$ 是满足 $w_1$ 质因数均出现在 $i$ 中的极大值，$w_3$ 则是满足 $w_3$ 质因数均出现在 $j$ 中，且不出现在 $i$ 中的极大值，$w_2$ 则是 $\dfrac {k^2}{w_1w_3}$，即剩下的部分。 不难发现 $w_1, w_2, w_3$ 两两之间互质，且 $w_1w_2w_3 = k^2$。 接下来就开始列式子。 $$ \begin{aligned} H(i)H(j) &= \dfrac{S(k^2i) S(k^2j)}{S^2(k^2)} \\ &= \dfrac{S(w_1 w_2 w_3 i) S(w_1w_2w_3 j)}{S^2(w_1w_2w_3)} \\ &= \dfrac{S(w_1i)S(w_2)S(w_3)S(w_3j)S(w_1)S(w_2)}{S^2(w_1w_2w_3)} \\ &= \dfrac{S(w_1i)S(w_3j)S(w_2)}{S(w_1w_2w_3)} \\ &= \dfrac{S(k^2ij)}{S(k^2)} \\ &= H(ij) \end{aligned} $$ $H(i)$ 是积性函数，证毕。 回到正题。我们发现，$S(ijk^2) = S(k^2)H(ij)$。代回原来式子，我们得到 $$ \sum_{k = 1}^{\min(n,m)} \sum_{i = 1}^{\lfloor n / k \rfloor} \sum_{j = 1}^{\lfloor m / k \rfloor} S(k^2)H(ij) [\gcd(i,j) = 1] $$ 我们成功的把 $S(k^2)$ 给提出来了！如此，我们有 $H(ij) = H(i)H(j)$，与 $k = 1$ 类似的去做即可。 最后式子就是 $$ \sum_{k = 1}^{\min(n,m)} S(k^2) \sum_{d = 1}^{\lfloor \min(n,m) / k \rfloor} \mu(d) \left( \sum_{i = 1}^{\lfloor n / dk \rfloor} H(id) \right) \left( \sum_{i = 1}^{\lfloor m / dk \rfloor} H(jd) \right) $$ 以下默认 $n,m$ 同阶。 等等，这个怎么计算呢？观察到它与一般的式子不太一样。如果光从这个式子出发的话，我们可能会去想预处理 $f_{d}(x) = \sum_{i = 1}^{\lfloor x / d \rfloor} H(di)$。这么做空间复杂度只有 $\mathcal O(n \log n)$，后面那个式子可以数论分块，但是瓶颈在预处理上面，总时间复杂度是 $\mathcal O(n \log n)$。翻一眼题解，我去，最快 $\mathcal O(n \log n \log \log n)$，我破记录了？ 很遗憾，$H(i)$ 是不能独立且 $\mathcal O(1)$ 算出来的，这个做法没办法落到实处。 那么我们怎么做呢？ 我们观察到，$H(i) = \dfrac{S(k^2i)}{S(k^2)}$，只跟 $k$ 有关，这就意味着，我们可以在枚举 $k$ **之后**再进行预处理。 那么假设我们的 $k$ 确定了，那么对于式子 $\sum_{i = 1}^{\lfloor n / dk \rfloor} H(id)$ 来讲，就可以做一个类似前缀和的处理了。假使我们暴力处理前缀和，那么我们的时间复杂度是多少呢？ 外侧显然只能暴力枚举，是一个调和级数。我们关注内侧的时间复杂度。 首先观察我们要处理多少个 $H$，观察到还是一个调和级数。所以一共有 $\mathcal O(n \log n)$ 个 $H$。 接下来观察计算 $H$ 的时间复杂度。首先我们知道 $H(i) = \dfrac{S(k^2i)}{S(k^2)}$。那理论上来讲，如果我们想把分子分母拆开来计算，首先就有一个快速幂的 $\log$。接着来看 $S(k^2i)$ 和 $S(k^2)$ 吧。首先由于 $S(k^2)$ 只和 $k$ 有关系，只用算一次。再看 $S(k^2i)$，这个在实际枚举的时候，我们实际询问的是 $S(k^2id)$，来分析一下这个值的范围。 观察到 $idk \leq n$。那么 $idk^2 \leq nk$ —— 好家伙，$k$ 最大值可以取到 $n$，这就意味着 $idk^2$ 最大可以到 $n^2$，那么这个不能简单线性预处理 $\mathcal O(n^2) - \mathcal O(1)$ 去做了。于是我们转而使用 $\mathcal O(\dfrac n{\ln n}) - \mathcal O(\log n)$ 的方法，具体的，我们预处理 $S(p^i)$，对于一个质数一直处理到 $p^i > n^2$ 为止。这部分的时间复杂度应该是 $\mathcal O(\dfrac n{\ln n})$。然后对于 $idk^2$ 我们每次做一次质因数分解，由于我们有现成的质数表，时间复杂度是 $\mathcal O(\ln n)$。根据积性函数的性质，我们乘起来即可。 好，难点基本就这么多，我们来看看时间复杂度，整体集中在预处理上，空间如果要存下 $H$ 的前缀和需要 $\mathcal O(n \log n)$，至于时间复杂度，计算 $H$ 的时间复杂度是 $\mathcal O(\log n)$，而一共有 $\mathcal O(n \log n)$ 个 $H$，外层还有一个调和级数，总共是 $\mathcal O(n \log^3 n)$。 有点丑陋啊！观察 $H(id)$ 这个部分。 对于 $d = 1$ 的时候，我们用到的是 $H(1), H(2), \dots, H(\left\lfloor \dfrac nk \right\rfloor)$。而 $d = 2$ 的时候，就是 $H(2), H(4), \dots , H(\left\lfloor \dfrac nk \right\rfloor)$，我们发现 $H$ 重复计算了！所以这里其实可以记忆化，所以最后时间复杂度可以去掉一个 $\log$ 变成 $\mathcal O(n \log^2 n)$。 这个实现方法是自己想的，比较 naive，没有达到最优的时间复杂度。 而且麻烦程度排第一，不想写代码……找个时间学习一下 P8570 的特解。 ## 7 第二部分例题 之后使用的莫比乌斯反演例题会放到这里。 ### 7.1 CF1139D Tutorial > 给定 $m$，现在要生成一个数列，每次随机选择一个 $[1, m]$ 的整数放在数列末尾，当数列的 $\gcd$ 为 $1$ 的时候停止。求期望数列长度，对 $10^9 + 7$ 取模。 > > $1 \leq m \leq 10^5$。 挺小清新的题目。题面很简洁，脱离了非常长的式子。 不妨令 $f_i$ 表示当数列整体 $\gcd = i$ 的时候，期望还需要加多少个数在后面才能满足要求。 显然我们列出式子： $$ f_i = 1 + \dfrac{\color{red}\sum_{j = 1}^m f_{\gcd(i,j)}}{m} $$ 我们不妨直接聚焦红色部分的式子，其他部分可以暂时不管。 一眼枚举 $\gcd$，注意到一定是 $i$ 的因数。 $$ \sum_{g \mid i} f_g \sum_{j = 1}^m [\gcd(i,j) = g] $$ 接下来就都是非常非常常规的操作了。这题其实不难。主要复健用吧。 后面那个部分一眼拆爆成 $$ \sum_{g \mid i} f_g \sum_{d \mid (i / g)} \mu(d) \left \lfloor \dfrac {m}{dg} \right \rfloor $$ 这次的设 $T = dg$ 有点不太一样。我们发现 $T$ 是有限制的。注意到 $d \mid (i / g)$，意味着 $dg \mid i$，即 $T \mid i$，所以有： $$ \sum_{T \mid i} \left \lfloor \dfrac{m}{T} \right \rfloor \sum_{g \mid T} \mu(\dfrac {T}{g}) f_g $$ 现在这个式子已经很漂亮了。我们可以枚举 $T$，然后边算边累加后面的那个狄利克雷卷积的形式的式子。这样就可以在 $\mathcal O(n \log n)$ 的复杂度里面计算这个式子。 但是现在有一个问题。观察到一开始这个式子它其实是一个转移式子，现在推导出来的这个式子是转移式子的一部分，所以我们要代回原来的式子做进一步的思考。 所以我们有： $$ f_i = 1 + \dfrac{\sum_{T \mid i} \left \lfloor \dfrac{m}{T} \right \rfloor \sum_{g \mid T} \mu(\dfrac {T}{g}) f_g}{m} $$ 我们肯定不能让 $f_i \rightarrow f_i$，把这种情况处理出来然后移动到等式左侧。观察到当且仅当 $g = T = i$ 的时候才会出现这种情况，此时的系数是 $\left \lfloor \dfrac mT \right \rfloor = \left \lfloor \dfrac mi \right \rfloor$。挪到等式的左边就是 $$ (1 - \dfrac{\left \lfloor \dfrac mi \right \rfloor}{m}) f_{i} = 1 + \dfrac{\sum_{T \mid i} \left \lfloor \dfrac{m}{T} \right \rfloor \sum_{g \mid T} \mu(\dfrac {T}{g}) f_g [g \neq i]}{m} $$ 除过去就有： $$ f_i = \dfrac{m + \sum_{T \mid i} \left \lfloor \dfrac{m}{T} \right \rfloor \sum_{g \mid T} \mu(\dfrac {T}{g}) f_g [g \neq i]}{m - \left \lfloor \dfrac mi \right \rfloor} $$ 此时我们来重点聚焦如何处理 $g = i$ 的情况。 观察到当 $T = g = i$ 的时候，此时后面的这一堆东西的值应该是 $0$。倘若我们没有用 $f_i$ 去更新后面的这个狄利克雷卷积，那么这个值显然就不会被计入。 所以我们的最佳处理方法应该就是：不处理。 最后时间复杂度应该是 $\mathcal O(n \log n)$。 --- 调半天发现线性筛写错了。乌鱼。 ## 8 后记 以后可能还会接着更新。 先这样了。非常感谢你能看到这里。 也十分感谢许多在写这篇文章帮助过我的朋友。 膜拜 zak！膜拜 Alpha！膜拜 wtc！膜拜 lwt！ 一个个全都是数论天才，我怎么活。