积性函数求和 大合集 Part 1

· · 算法·理论

如有谬误之处，恳请读者指正。

参考资料：

前言

本文将介绍若干算法，包括：

上述算法大多围绕如下核心问题展开：

S_f(n) = \sum_{i=1}^{n} f(i)

即积性函数 f 的前缀和计算。研究这一问题的过程中，我们也自然发展出了处理前缀质数和的高效方法：

S_{\mathrm{prime}\,f}(n) = \sum_{p \le n} f(p),

本文未设置例题，但将尽量从本质角度进行讲解。

约定与记号

  3. 对于任意 x\in R(n)，都有 R(x) \subseteq R(n)。

  5. 对于 B \ge \sqrt n 有 \Theta\left(\sum_{x \in R(n), x > B} \sqrt x\right) = \Theta\left(\frac{n}{\sqrt B}\right)。

证明参见 『附录 A：整除集合 R(n) 的性质证明』

f^{(\ast n)} = \underbrace{f \ast \dots \ast f}_{n \text{ 个}} \prod_{i=1}^{n}{}^{\!\!(*)} f_i = f_1 \ast \cdots \ast f_n

0. 一般化线性筛

定理： 在线性筛求积性函数 f 前 n 项的过程中，若计算单个素数幂处的函数值 f(p^k) 的时间复杂度为 O(\mathrm{poly}\, k)，则计算范围内所有素数幂 p^k \le n 处函数值的总时间复杂度为 \Theta\left(\frac{n}{\ln n}\right)。

证明：

设计算 f(p^k) 的时间复杂度为 P(k)，其中 P 是关于 k 的多项式。

计算所有 n 以内的素数幂 p^k 的总代价 T(n) 为：

T(n) = \sum_{i = 1}^{\pi(n)} \sum_{k = 1}^{\left\lfloor\log_{p_i}(n)\right\rfloor} P\left(k\right)

对于 p_i \ge \sqrt n，有 \left\lfloor\log_{p_i}(n)\right\rfloor = 1，按 \sqrt n 分界计算：

\begin{align*} T(n) &= \left(\sum_{i = \pi(\sqrt n) + 1}^{\pi(n)} P(1)\right) + \left(\sum_{i = 1}^{\pi(\sqrt n)} \sum_{k = 1}^{\left\lfloor\log_{p_i} n\right\rfloor} P(k) \right) \\ &= P(1) \cdot \left(\frac{n}{\ln n} - \frac{\sqrt n}{\ln n}\right) + O\left(\sum_{i = 1}^{\pi(\sqrt n)} \left\lfloor\frac{\ln n}{\ln p_i}\right\rfloor P\left(\left\lfloor\frac{\ln n}{\ln p_i}\right\rfloor\right)\right) \\ &= \Theta\left(\frac{n}{\ln n}\right) + O\left(\sum_{i = 1}^{\pi(\sqrt n)}\ln n P\left(\ln n\right)\right) \\ &= \Theta\left(\frac{n}{\ln n}\right) + O(\sqrt n \, \mathrm{polylog} \, n) = \Theta\left(\frac{n}{\ln n}\right) \end{align*}

命题得证。

推论：

由于线性筛框架的遍历复杂度为 \Theta(n)，且素数幂处的计算代价仅为 \Theta\left(\frac{n}{\ln n}\right)，因此在上述条件下，线性筛求 f 前 n 项的总时间复杂度恒为 \Theta(n)。

故在此后的讨论中，我们视线性筛的时间复杂度为 \Theta(n)，不再赘述。

应用：

该结论为计算两个积性函数的狄利克雷卷积 f \ast g 的前 n 项提供了 O(n) 的算法。

问题：

已知积性函数 f, g 的前 n 项，求 f \ast g 的前 n 项。

对于素数幂处的取值 (f \ast g)(p^k)，根据定义有：

(f \ast g)\left(p^k\right) = \sum_{i = 0}^{k} f\left(p^i\right)g\left(p^{k - i}\right)

直接暴力计算该式的时间复杂度为 O(k)，满足 O(\mathrm{poly}\, k) 的条件。因此，我们可以通过线性筛在 O(n) 时间内计算积性函数的 Diruchlet 卷积。

1. Dirichlet 双曲法（块筛单点求值）

考虑一个经典问题，如何求如下式子：

S_{f \ast g}(n) = \sum_{ij \le n} f(i)g(j)

考虑其几何解释，设平面上点 (i, j) 表示 f(i)g(j)，则上式是在求反比例函数 xy = n 下的所有整点之和。

传统的整除分块实际上是对曲线下整点做了如下分割：

写作式子是：

S_{f \ast g}(n) = \sum_{i = 1}^n f(i) S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)

而还有一种视角被称作 Dirichlet 双曲法的视角，考虑了如下划分：

写作式子是：

S_{f \ast g}(n) = \sum_{i = 1}^{\lfloor \sqrt n \rfloor} f(i)S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right) + \sum_{i = 1}^{\lfloor \sqrt n \rfloor} g(i)S_f\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - S_f(\lfloor \sqrt n \rfloor)S_g(\lfloor \sqrt n \rfloor)

然后我们有结论 [1, \lfloor \sqrt n \rfloor] \subseteq R(n)，以上式子函数内的自变量取值都在 R(n) 内，只依赖 f, g 的块筛。其中 f(x), g(x) 在 x \in [1, \lfloor \sqrt n \rfloor] 的值可以通过 S_f, S_g 差分得到。

综上该问题可以 O(\sqrt n) 求解，由于 Dirichlet 双曲法便于形式化描述，本文将使用 Dirichlet 双曲法。

2. 块筛卷积

求解问题：

已知 积性函数 f, g 关于 n 的块筛，求出 f \ast g 的块筛。

若对每个 x \in R(n) 独立应用上一节的双曲法，则总复复杂度为 O(\sum_{x \in R(n)} \sqrt x) = O(n^{3 / 4})。

若预处理 f * g 在所有 [1,B] 处的函数值（B \ge \sqrt n），则仅需对 x > B 的部分使用双曲法，复杂度为 O\left(B + \sum_{x \in R(n), x > B}\right) = O(B + \frac{n}{\sqrt B})，取 B = n^{2 / 3} 平衡得到 O(n^{2 / 3})。

3. 杜教筛（块筛除法）

求解问题：

给定 积性函数 f, g，已知 f \ast g, g 关于 n 的块筛，求出 f 的块筛。

我们从双曲法公式中将 S_f(n) 单独提出：

\begin{align*} S_{f \ast g}(n) &= \sum_{i = 1}^{\lfloor \sqrt n \rfloor} f(i)S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right) + \sum_{i = 1}^{\lfloor \sqrt n \rfloor} g(i)S_f\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - S_f(\lfloor \sqrt n \rfloor)S_g(\lfloor \sqrt n \rfloor)\\ &= S_{f}(n) + \sum_{i = 1}^{\lfloor \sqrt n \rfloor} f(i)S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right) + \sum_{i = 2}^{\lfloor \sqrt n \rfloor} g(i)S_f\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - S_f(\lfloor \sqrt n \rfloor)S_g(\lfloor \sqrt n \rfloor) \end{align*}

移项得到：

S_{f}(n) = S_{f \ast g}(n) - \sum_{i = 1}^{\lfloor \sqrt n \rfloor} f(i)S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - \sum_{i = 2}^{\lfloor \sqrt n \rfloor} g(i)S_f\left(\left\lfloor\frac{n}{i}\right\rfloor\right) + S_f(\lfloor \sqrt n \rfloor)S_g(\lfloor \sqrt n \rfloor)

按照 R(n) 中自变量从小到大的顺序递推计算。沿用上一节块筛卷积的平衡方式，时间复杂度为 O(n^{2/3})。

4. Lucy-Hedgehog 算法

Lucy-Hedgehog 算法由 Project Euler 用户 Lucy-Hedgehog 提出，其原始讨论帖见 Link。

该算法可以看作是对 Eratosthenes 筛思想在“函数求和”上的推广，用于在仅已知 f 的块筛信息时，进一步求解其质数块筛。

4.1 Introduction

求解问题：

函数 f 是 完全积性函数（典型如 \mathrm{id}_k），已知 f 关于 n 的块筛，求 f 的质数块筛。

回顾 Eratosthenes 筛的过程，对于每个质数 p，都会从序列中删除其真倍数。

Lucy–Hedgehog 算法的核心思想是：将 Eratosthenes 筛中“删除质数倍数”的过程，等价转化为对函数前缀和中对应倍数贡献的消去。

4.2 递推式推导

定义函数 S(n, k) 表示，用所有小于 p_k 的质数筛去区间 [2,n] 后，剩余整数 i 的函数值 f(i) 之和。

剩下的数 i 要么是质数，要么是最小质因数 \operatorname{lpf}(i) \ge p_k 的合数，我们可以列出式子：

S(n, k) = \sum_{i = 2}^n [i \in \mathbb{P} \lor \operatorname{lpf}(i) \ge p_k]f(i) \tag{4.2.1}

不满足 \operatorname{lpf}(p_i) \ge p_k 的质数 p_i 满足 i < k，上式可以拆分为：

S(n, k) = \left(\sum_{i = 2}^n [\operatorname{lpf}(i) \ge p_k]f(i)\right) + S_{\mathrm{prime} \, f}(p_{k - 1}) \tag{4.2.2}

关键观察：若 k > \pi\left(\sqrt n\right)，那么很明显 [2, n] 的合数均已被筛去，因此区间 [2,n] 中仅剩质数，S(n, k) 就是 S_{\mathrm{prime} \, f}(n)。该观察的推论是函数 S(n, k) 关于固定的 n 只有 O\left(\frac{\sqrt n}{\ln n}\right) 个不同的取值。

初始 S(n, 1) = S_f(n)，我们希望求出 S(n, \pi\left(\sqrt n\right) + 1) = S_{\mathrm{prime} \, f}(n)。

对于 p_k \le \sqrt n，质数 p_k 能成功从 S(n, k) 中减掉 p_k 的真倍数得到 S(n, k + 1)，那么 S(n, k) 与 S(n, k + 1) 的差值就是所有满足 [\operatorname{lpf(i) = p_k \land i \neq p_k}] 的 f(i)：

\begin{align*} S(n, k) - S(n, k + 1) &= \sum_{i = 1}^n [i \in \mathbb{P} \lor \operatorname{lpf}(i) \ge p_k]f(i) - [i \in \mathbb{P} \lor \operatorname{lpf}(i) \ge p_{k + 1}]f(i) \\ &= -f(p_k) + \sum_{i = 2}^n [\operatorname{lpf}(i) = p_k]f(i) \tag{4.2.1} \\ &= -f(p_k) + f(p_k) + \sum_{t = 2}^{\left\lfloor \frac{n}{p_k} \right\rfloor} [\operatorname{lpf}(t) \ge p_k]f(t \times p_k) \tag{4.2.2}\\ &= f(p_k)\sum_{t = 2}^{\left\lfloor \frac{n}{p_k} \right\rfloor} [\operatorname{lpf}(t) \ge p_k]f(t) \tag{4.2.3} \end{align*} 1. $t = 1$，此时 $i = p_k$，贡献为 $f(p_k)$。 2. $t > 1$，此时 $t = p_k \cdot t$，如果 $\operatorname{lpf(i)} = p_k$，很明显需要满足 $\operatorname{lpf(t)} \ge p_k$。 结合二者可得到 $(4.2.2)$。 注意到式 $(4.2.3)$ 中出现的求和结构与 $S(\,\cdot\,,k)$ 的定义形式一致，可以将其重写为关于 $S$ 的递推 DP 关系： $$ S(n, k + 1) = S(n, k) - f(p_k)\left(S\left(\left\lfloor \frac{n}{p_k} \right\rfloor, k\right) - S_{\mathrm{prime} \, f}(p_{k - 1})\right) $$ 若目标状态为 $S\!\left(n,\pi(\sqrt n)+1\right)$，递推过程中会不断产生形如 $$ S\left(\left\lfloor \frac{n}{p_{i_1}p_{i_2}\cdots p_{i_t}} \right\rfloor,\; \cdot\right) $$ 的子问题。 由于所有分母均为整数乘积，其取值必属于集合 $R(n)$，因此递归过程中访问的所有第一维自变量，恰为 $R(n)$ 中的元素，这与质数块筛所需的自变量集合完全一致。 因此，DP 状态数是 $O\left(\sum_{x \in R(n)} \frac{\sqrt x}{\ln x}\right) = O\left(\frac{n^{3/4}}{\ln n}\right)$。算法还需要知道完全积性函数 $f$ 在 $p \le \sqrt n$ 处的点值，线性筛 $O\left(\sqrt n\right)$ 即可。 一个明显的应用是，如果对 $k + 1$ 次多项式 $f$ 求 $S_{\mathrm{prime} \, f}(n)$，可以拆成 $\mathrm{id}_0 \sim \mathrm{id}_k$ 分别求，时间复杂度 $O\left(\frac{k n^{3/4}}{\ln n}\right)$。 ## 5. 洲阁筛 / min_25 筛 根据 OI Wiki 的说法，“洲阁筛”和“min_25”筛是同一种算法的两种不同时间复杂度的实现方式。 本文将介绍这两种实现，分别为 $O\left(n^{1 - \epsilon}\right)$ 和 $O\left(\frac{n^{3 / 4}}{\ln n}\right)$，前者虽然理论复杂度不优，但是在 OI 范围内跑得很快。所以你可能会看到很多声称自己做法是 $O\left(\frac{n^{3 / 4}}{\ln n}\right)$ 的题解，代码实现却是 $O\left(n^{1 - \epsilon}\right)$ 的。 > **求解问题：** > > 函数 $f(n)$ 是**积性函数**，可以 $O(\mathrm{poly} \, k)$ 计算 $f(p^k)$，已知 $f$ 关于 $n$ 的质数块筛，求 $f$ 关于 $n$ 的块筛。 ### 5.1 朴素算法 定义函数 $F_k(n)$： $$ F_k(n) = \sum_{i = 2}^n [p_k \le \operatorname{lpf}(i)]f(i) $$ 答案即为 $F_1(n) + f(1)$，初始条件有 $F_{\pi(\sqrt n) + 1}(n) = S_{\mathrm{prime} \, f}(n)$。 考虑如何求出 $F_k(n)$。通过枚举每个 $x$ 的最小质因子幂可以得到递推式： $$ \begin{align*} F_k(n) &= \sum_{x = 2}^n [p_k \le \operatorname{lpf}(x)]f(x) \tag{5.2.1}\\ &= \sum_{\substack{i \ge k \\ p_i \le n}} \sum_{x = 2}^n [\operatorname{lpf}(x) = p_i]f(x) \tag{5.2.2}\\ &= \sum_{\substack{i \ge k \\ p_i \le n}} \sum_{\substack{c \ge 1\\ {p_i}^c \le n}} f({p_i}^c) \left( 1 + \sum_{t = 2}^{\left\lfloor \frac{n}{{p_i}^c} \right\rfloor}[p_i < \operatorname{lpf}(t)]f(t) \right) \tag{5.2.3} \end{align*} $$ $(5.2.2)$ 是在枚举 $(5.2.1)$ 中 $x$ 的最小质因子 ${p_i}$。$(5.2.3)$ 进一步枚举其次数 $c$，设 $x = {p_i}^c \times t$，则 $t$ 满足 $\operatorname{lpf(t)} > p_i$ 或 $t = 1$，其中 $t$ 的取值范围是 $\left[1, \left\lfloor \frac{n}{{p_i}^c} \right\rfloor \right]$。这里有两种情况： 1. $t = 1$，此时 $x = {p_i}^c$，$t$ 的贡献为 $f(t) = f(1) = 1$。 2. $t > 1$，此时 $t$ 的最小质因数 $\operatorname{lpf}(t)$ 应当大于 $p_i$。 注意到括号内的求和式 $F_k$ 的定义式一模一样，可以得到： $$ \begin{align*} F_k(n) &= \sum_{p_k \le p_i \le n} \sum_{\substack{c \ge 1\\ {p_i}^c \le n}} f({p_i}^c) \left( 1 + F_{i + 1}\left(\left\lfloor \frac{n}{{p_i}^c} \right\rfloor\right) \right) \end{align*} $$ 上式直接求是 $O(n)$ 的。对 $F_k(n)$ 的求解，本质相当于将 $[1, n]$ 按照最小质因子幂 $p_i^c (i \ge k)$ 划分成若干等价类，每个等价类递归求解。这与 $[1, n]$ 的质因数分解一一对应，所以这个递归树有 $n$ 个叶子。 接下来将介绍第一种做法： ### 5.2 第一种做法（所谓“min_25”） 回到 $F_k$ 的定义式，我们将其划分为合数和质数两部分： $$ \begin{align*} F_k(n) &= \sum_{x = 2}^n [p_k \le \operatorname{lpf}(x)]f(x)\\ &= \left(\sum_{i = 2}^n [p_k \le \operatorname{lpf}(i)][i \not\in \mathbb P]f(i)\right) + \left(\sum_{p_k \le p_i}f(p_i)\right)\\ &= \left(\sum_{i = 2}^n [p_k \le \operatorname{lpf}(i)][i \not\in \mathbb P]f(i)\right) + S_{\mathrm{prime} \, f}(n) - S_{\mathrm{prime} \, f}(p_{k - 1}) \\ \end{align*} $$ 合数部分的求和式与原来的变化不大，我们只需要剔除 $[x \in \mathbb P]$ 的贡献即可，具体见下式： $$ \sum_{p_k \le p_i \le n} \sum_{\substack{c \ge 1\\ {p_i}^c \le n}} f({p_i}^c) \left( [c \neq 1] + F_{i + 1}\left(\left\lfloor \frac{n}{{p_i}^c} \right\rfloor\right) \right) $$ 这里是枚举 $x = p_i^c \times t$ 时，当 $c = 1$ 且 $t = 1$ 时，不计算 $f(t) = 1$ 的贡献，这样正好去掉了 $f(p_i)$。 根据数论经典结论，合数是 $n$ 当且 $\operatorname{lpf}(n)^2 \le n$，正确性显然。由于第一层 sigma 可以修改为 $\displaystyle\sum_{p_k \le {p_i}^2 \le n}$。整理得到新的递推式： $$ F_k(n) = \left(\sum_{p_k \le {p_i}^2 \le n} \sum_{\substack{c \ge 1\\ {p_i}^c \le n}} f({p_i}^c) \left( [c \neq 1] + F_{i + 1}\left(\left\lfloor \frac{n}{{p_i}^c} \right\rfloor\right) \right)\right) + S_{\mathrm{prime} \, f}(n) - S_{\mathrm{prime} \, f}(p_{k - 1}) $$ 最主要的优化就是第一层求和枚举最小质因数 $p_i$ 只需要枚举到 $\sqrt n$，这是个巨大的优化。直接对着递推式算的复杂度被证明是 $O\left(n^{1 - \epsilon}\right)$（见朱震霆集训队论文[《一些特殊的数论函数求和问题》](https://github.com/OI-wiki/libs/blob/master/%E9%9B%86%E8%AE%AD%E9%98%9F%E5%8E%86%E5%B9%B4%E8%AE%BA%E6%96%87/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2018%E8%AE%BA%E6%96%87%E9%9B%86.pdf)2.3）。 对于 $S_{\mathrm{prime} \, f}$，算法需要知道 $p \le \sqrt n$ 与 $x \in R(n)$ 处的点值，第一部分 $O\left(\sqrt n\right)$ 线性筛即可，第二部分是题目给定的质数块筛；算法还需要知道 $f(p^k)$ 在 $p \le \sqrt n$ 的点值，也可以 $O(\sqrt n)$ 预处理。 以上做法最早由 min_25 在其博客中提出，因此这种做法常被称作“min_25 筛”。 ### 5.3 第二种做法（所谓“洲阁筛”） 我们需要抛弃旧思路寻找新的突破口，这里不再沿用 $F_k$。定义新函数 $G(n, k)$ 为（自变量范围与 Lucy-Hedgehog 一样）： $$ G(n, k) = \sum_{i = 2}^n [i \in \mathbb P \lor p_k \le \operatorname{lpf}(i)]f(i) $$ 即用 $< p_k$ 的质数筛 $2 \sim n$ 后剩余的所有数 $i$ 的 $f(i)$ 之和。 与 Lucy-Hedehog 一样，这个函数满足对任意 $k > \pi\left(\sqrt n\right)$ 都有 $G(n, k) = S_{\mathrm{prime} \, f}(n)$。不过这次我们要从 $S_{\mathrm{prime} \, f}(n)$ 还原出 $S_f(n)$，即从 $G(n, \pi\left(\sqrt n\right) + 1)$ 递推出 $G(n, 1)$。 从 $G(n, k)$ 到 $G(n, k + 1)$，$p_k$ 筛掉了所有最小质因数等于 $p_k$ 的数（除了 $p_k$ 自己），即： $$ G(n, k) - G(n, k + 1) = \left(\sum_{i = 2}^n [\operatorname{lpf}(i) = p_k]f(i)\right) - f(p_k) \tag{5.3.1} $$ 通过枚举每个最小质因子及其次数化简 $(5.3.1)$ 右式： $$ \begin{align*} &\left(\sum_{i = 2}^n [\operatorname{lpf}(i) = p_k]f(i)\right) - f(p_k) \tag{5.3.2}\\ =& \left(\sum_{\substack{c \ge 1\\ {p_k}^c \le n}} f({p_i}^c)\left(1 + \sum_{t = 2}^{\left\lfloor \frac{n}{{p_i}^c} \right\rfloor} \left[\operatorname{lpf}(t) > p_k \right]f(t)\right)\right) - f(p_i) \tag{5.3.3}\\ =& \sum_{\substack{c \ge 1\\ {p_k}^c \le n}} f({p_i}^c)\left([c \neq 1] + \sum_{t = 2}^{\left\lfloor \frac{n}{{p_i}^c} \right\rfloor} \left[\operatorname{lpf}(t) > p_k \right]f(t)\right) \tag{5.3.4} \end{align*} $$ 根据 $(5.2.2)$，$(5.2.3)$，可以推出 $(5.3.2)$，$(5.3.3)$。 我们尝试凑出 G 的定义式，下式根据 $(4.2.1)$，$(4.2.2)$ 推出： $$ \begin{align*} \sum_{i = 2}^{\left\lfloor \frac{n}{{p_i}^c} \right\rfloor} [p_k < \operatorname{lpf}(i)]f(i) &= \left(\sum_{i = 2}^{\left\lfloor \frac{n}{{p_i}^c} \right\rfloor} [i \in \mathbb P \lor \operatorname{lpf}(i) < p_k]f(i)\right) - \left(\sum_{p_i \le p_{k}} f(p_i)\right)\\ &= G\left(\left\lfloor \frac{n}{{p_i}^c} \right\rfloor, k + 1\right) - S_{\mathrm{prime} \, f}(p_k) \end{align*} $$ 将其带入 $(5.3.4)$，移项得到： $$ \begin{align*} G(n, k) &= G(n, k + 1) + \sum_{\substack{c \ge 1\\ {p_k}^c \le n}} f({p_i}^c)\left([c \neq 1] + G\left(\left\lfloor \frac{n}{{p_i}^c} \right\rfloor, k + 1\right) - F_{\mathrm{prime}}(p_k)\right)\\ \end{align*} $$ 现在我们得到了个与 Lucy-Hedgehog 十分相似的 DP 转移式，其状态数与 Lucy-hedgehog 同为 $O\left(\frac{n^{3/4}}{\ln n}\right)$。 现在考虑转移的复杂度，对于固定的 $G(n, k)$，其中 $c$ 的枚举范围是 $\left[1, \log_{p_k}(n)\right]$。那么对于给定 $n$，遍历 $k \in \left[1, \pi\left(\sqrt n\right)\right]$，则枚举 $c$ 需要花费 $O(c)$ 的复杂度，总复杂度是： $$ \begin{align*} O\left(\sum_{i = 1}^{\pi\left(\sqrt n\right)} \sum_{c = 1}^{\left\lfloor \log_{p_i}(n) \right\rfloor} O(c) \right) &= O\left(\sum_{i = 1}^{\pi\left(\sqrt n\right)} \left(\left\lfloor\frac{\ln n}{\ln p_i}\right\rfloor\right)^2\right)\\ &= O\left((\ln n)^2 \sum_{p \le \sqrt n} \frac{1}{\left(\ln p\right)^2}\right)\\ &= O\left((\ln n)^2 \int_{2}^{\sqrt n} \frac{1}{(\ln x)^2} \mathrm{d}x \right)\\ &= O\left((\ln n)^2 \frac{\sqrt n}{(\ln n)^3} \right) = O\left(\frac{n}{\ln n}\right) \end{align*} $$ 可见比 Lucy-Hedgehog 多枚举了个 $c$ 也并没有增加时间复杂度。 内层 DP 的时间复杂度与 Lucy-Hedgehog 一致为 $O\left(\frac{\sqrt{n}}{\ln n}\right)$，整体复杂度同为 $O\left(\sum_{x \in R(n)}\frac{\sqrt n}{\ln n}\right) = O\left(\frac{n^{3 / 4}}{\ln n}\right)$。 这种做法应该最早出自于任之洲的论文[《积性函数求和的几种方法》](https://github.com/OI-wiki/libs/blob/master/%E9%9B%86%E8%AE%AD%E9%98%9F%E5%8E%86%E5%B9%B4%E8%AE%BA%E6%96%87/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2016%E8%AE%BA%E6%96%87%E9%9B%86.pdf)，常被称作“洲阁筛”。 ### 5.4 工具分析 阅读完上文，读者应该能感受到“Lucy-Hedgehog”，“min_25 筛”和“洲阁筛”相似之处的。 仔细观察“洲阁筛”和“Lucy-Hedgehog”的定义式与转移过程可以发现，“洲阁筛”在结构上可视为“Lucy–Hedgehog”的反向筛过程。 二者的核心差异在于支持的函数类型与筛的方向不同： - Lucy–Hedgehog：由 **块筛** 推导 **质数块筛**，仅适用于 **完全积性函数**。 - 洲阁筛 / min_25 筛：由 **质数块筛** 还原 **块筛**，适用于 **积性函数**，要求能 $O(k)$ 计算 $f\left(p^k\right)$。 到目前为止，我们得到了还算强大的工具，足够处理以下问题： > **标准积性函数求和问题：** > > 积性函数 $f$ 满足 $f(p)$ 为关于 $p$ 的多项式（项数较少），$f(p^k)$ 可以 $O(k)$ 计算。 > > 求 $f$ 关于 $n$ 的块筛。 先考虑，如何求 $f$ 的质数块筛？ Lucy–Hedgehog 算法能够处理形如 $g(p)=c\,p^k$ 的质数块筛。 由于保证 $f(p)$ 为多项式，可将其拆分为若干单项式之和，分别使用 Lucy–Hedgehog 计算， 再合并得到 $f$ 的质数块筛。设多项式非零项系数有 $m$ 个，则该部分复杂度 $O\left(\frac{m \, n^{3/4}}{\ln n}\right)

然后，我们使用“min_25筛”或“洲阁筛”，即可将质数块筛还原成块筛，复杂度 O\left(\frac{n^{3/4}}{\ln n}\right)。

综上，我们得到了标准积性函数求和的 O\left(\frac{m \, n^{3/4}}{\ln n}\right) 复杂度的做法。

6. PN 筛

6.1 性质

定义：

Powerful Number（以下简称 PN）是所有质因子次数大于等于 2 的数。对于正整数 n，记 n 的质因数分解为 n = \prod_{i=1}^{m} p_{i}^{e_{i}}，n 是 PN 当且仅当 \forall 1 \le i \le m, e_{i} > 1。

性质 1：

所有 PN 都可以表示成 a^{2}b^{3} 的形式。

证明：

若 e_i 是偶数，则将 p_{i}^{e_{i}} 合并进 a^{2} 里；若 e_i 为奇数，则先将 p_{i}^{3} 合并进 b^{3} 里，再将 p_{i}^{e_{i}-3} 合并进 a^{2} 里。

推论： [1,n] 内的 PN 最小质因子 \le \sqrt n。

性质 2：

**证明：** 考虑枚举 $a$，再考虑满足条件的 $b$ 的个数，$[1, n]$ 内 PN 数的个数等于 $$ O\left(\sum_{1 \le a^{2}\le n} \left\lfloor \sqrt[3]{\frac{n}{a^{2}}}\right\rfloor\right) = O\left(\int_{1}^{\sqrt n} \sqrt[3]{\frac{n}{x^2}} \mathrm{d}x \right) = \Theta\left(\sqrt n\right) $$ ### 6.2 素数拟合 积性函数 $f, g$ 对所有质数 $p$ 满足 $f(p) = g(p)$，则称 $f, g$ 在素数处互相拟合。 > **解决问题：** > > 积性函数 $f, g$ 在素数处互相拟合，已知 $g$ 关于 $n$ 的块筛，求 $f$ 的块筛。 令 $h = f \ast g^{(\ast -1)}$，根据 Dirichlet 卷积的性质，$h$ 是积性函数，存在且唯一。 注意到 $f(p) = g(p)h(1) + h(p)g(1) = g(p) + h(p)$，由于 $f(p) = g(p)$，可以得到 $h(p) = 0$。又因为是积性函数，所以 $h$ 只在 PN 处有值。 由于有值的 $h$ 只有 $O(\sqrt n)$ 个，考虑预处理出 $\sqrt n$ 以内的素数幂取值 $h(p^k)$，然后在 PN 集合上跑线性筛，求出所有 $n$ 以内的 PN 处取值，复杂度 $O\left(\sqrt n\right)$。 根据第一节的结论，有： $$ \begin{align*} S_f(n) &= \sum_{i = 1}^n h(i) S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ &= \sum_{i = 1}^n [i \in \mathrm{PN}] h(i) S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{align*} $$ $S_f(n)$ 可以 $O\left(\sqrt n\right)$ 单点求值，至此时间复杂度是 $O\left(\sum_{x \in R(n)}\sqrt x\right) = O\left(n^{3/4}\right)

使用杜教筛同样的阈值平衡，时间复杂度 O\left(n^{2/3}\right)。

cmd 在博客里说以上算法可以做到 O(n^{3 / 5})，但是那部分我没懂 /yun/kel/dk。

看懂了，证明放在『附录 B：PN 筛优化』。

7. 冷群筛

名字来源：

7.1 贝尔级数

对于积性函数 f，定义其关于质数 p 的贝尔级数为

\mathcal{B}_p[f](x) = \sum_{i = 0}^{+\infin} f\left(p^i\right) x^i

下文引入如下约定：若对任意素数 p，积性函数 f 的贝尔级数 \mathcal{B}_p[f](x) 具有相同的形式，即可表示为 x, p 的多项式 \mathcal{B}_p[f](x) = F(x, p)。凡不具备此性质者，则认为其性质不够良好，本文不作讨论。

需要说明的是，仅在 O(1) 个特殊质数处失去该性质的函数仍可通过分类处理转换成标准形式，如 LOJ 6053 简单的函数。

**定理 对于积性函数 f, g，有 \mathcal{B}_p[f \ast g] = \mathcal{B}_p[f] \cdot \mathcal{B}_p[g]。

证明：

\begin{align*} \mathcal{B}_p[g \ast f](x) &= \sum_{i = 0}^{+\infin} (f \ast g)\left(p^i\right) x^i\\ &= \sum_{i = 0}^{+\infin} \sum_{j = 0}^{i} f\left(p^j\right) x^j g\left(p^{i - j}\right) x^{i - j}\\ &= \left(\sum_{i = 0}^{+\infin} f(p_i) x^i\right)\left(\sum_{i = 0}^{+\infin} g(p_i) x^i\right)\\ &= \mathcal{B}_p[f] \cdot \mathcal{B}_p[g] \end{align*}

推论：

\mathcal{B}_p[f^{(\ast -1)}] = \mathcal{B}_p[f]^{-1}

常见积性函数的贝尔级数：

\def\arraystretch{2} \begin{array}{l l} \mathcal{B}_p[\varepsilon](x) &= 1 \\ \mathcal{B}_p[\mathrm{id}_k](x) &= \dfrac{1}{1 - p^k x} \\ \mathcal{B}_p[\mu](x) &= \mathcal{B}_p[\mu](\mathrm{id}_0)^{-1} = 1 - x \\ \mathcal{B}_p[\mu^2](x) &= 1 + x \\ \mathcal{B}_p[\sigma_k](x) &= \mathcal{B}_p[\mathrm{id}_0]\mathcal{B}_p[\mathrm{id}_k] = \dfrac{1}{(1 - x)(1 - p^k x)} \\ \mathcal{B}_p[\varphi](x) &= \mathcal{B}_p[\mathrm{id}_0]\mathcal{B}_p[\mu] = \dfrac{1 - x}{1 - px} \end{array}

7.2 倍增块筛卷积（冷群筛）

还是这个问题

标准积性函数求和问题：

积性函数 f 满足 f(p) 为关于 p 的多项式（项数较少），f(p^k) 可以 O(k) 计算。

求 f 关于 n 的块筛。

根据素数拟合，只需要构造出 g 满足 f(p) = g(p)，求出 g 的块筛，然后使用 PN 进行转化，即可得到 f 的块筛。

我们只关心 g(p) 的取值，即只关心贝尔级数 [x^1] 项的系数。

记 f(p) = \sum_{i = 0}^m a_i p^i（即 [x^1]\mathcal{B}_p[f](x)）。

注意到：

\begin{align*} \mathcal{B}_p[(\mathrm{id}_k)^{(\ast c)}](x) &= \left(\frac{1}{1 - p^kx}\right)^c\\ &= \sum_{i = 0}^{+\infin} \binom{c + i - 1}{i} (p^kx)^i\\ &= 1 + \left(c \cdot p^k\right) \, x + O(x^2) \end{align*}

其中 O(x^2) 表示 x^2 及更高次的项。

如果令 g = \underbrace{(\mathrm{id}_0 \ast \dots \ast \mathrm{id}_0)}_{a_0 \text{ 个}} \ast \underbrace{(\mathrm{id}_1 \ast \dots \ast \mathrm{id}_1)}_{a_1 \text{ 个}} \ast \dots \ast \underbrace{(\mathrm{id}_m \ast \dots \ast \mathrm{id}_m)}_{a_m \text{ 个}}。

那么有

\begin{align*} [x^1]\mathcal{B}_p[g] &= [x^1]\left(\prod_{i = 0}^{m} 1 + (a_i \cdot p^i) x\right)\\ &= \sum_{i = 0}^{m} a_i p^i \end{align*}

这正是我们想要构造的 g。

其中 \mathrm{id}_k(0 \le k \le m) 关于 n 的块筛是可以 O(k \sqrt n) 求的（经典的自然数 k 次幂求和问题），单次块筛卷积时间复杂度 O\left(n^{2/3}\right)，我们可以利用快速幂（倍增）的思想，在 O(\sum_{i = 0}^m \log |a_i|) 次块筛卷积后可以得到 g 的块筛。

至此我们得到了标准积性函数求和的 \tilde{O}(n^{2 / 3}) 算法。

附录 A：整除集合 R(n) 的性质证明

0. 定义回顾

定义：

R(n)=\left\{\left\lfloor\frac{n}{i}\right\rfloor \mid 1\le i\le n\right\}

该集合刻画了整除分块 / 块筛中所有可能出现的商值。

集合 R(n) 呈现两种结构：

等价的定义二：

R(n)=\left\{1, 2, \cdots, \lfloor \sqrt n \rfloor, \left\lfloor\frac{n}{1}\right\rfloor, \left\lfloor\frac{n}{2}\right\rfloor, \cdots, \left\lfloor\frac{n}{\lfloor \sqrt n \rfloor}\right\rfloor \right\}

1. 性质一：

|R(n)|=\Theta(\sqrt n)

由 R(n) 的第二条定义式可以直接得到。

2. 性质二：

[1,\lfloor\sqrt n\rfloor]\subseteq R(n)

也是根据第二条定义式可以直接得出。

3. 性质三：

若 x\in R(n)，则 R(x) \subseteq R(n)。

设 x = \left\lfloor\frac{n}{m}\right\rfloor，则对所有 \left\lfloor\frac{x}{i}\right\rfloor \in R(x) 都有：

\left\lfloor\frac{x}{i}\right\rfloor = \left\lfloor\frac{\left\lfloor\frac{n}{m}\right\rfloor}{i}\right\rfloor = \left\lfloor\frac{n}{mi}\right\rfloor \in R(n)

得证。

4. 性质四：

\sum_{x\in R(n)}\sqrt x=\Theta(n^{3/4})

考虑 R(n) 的第二条定义式，我们有

\begin{aligned} \sum_{x\in R(n)}\sqrt x &= \sum_{i = 1}^{\lfloor\sqrt n\rfloor} \sqrt i + \sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\\ &= \Theta\left(\int_{1}^{\sqrt n} \sqrt x + \sqrt{\left\lfloor\frac{n}{x}\right\rfloor} \mathrm{d}x \right)\\ &= \Theta(n^{3/4}) \end{aligned}

5. 性质五：

若 B\ge\sqrt n，则 \displaystyle \sum_{\substack{x\in R(n)\\x>B}}\sqrt x =\Theta\left(\frac{n}{\sqrt B}\right)。

$$ \left\lfloor\frac{n}{i}\right\rfloor \ge B \; (1 \le i \le \sqrt n) $$ 上式移项可推出 $1 \le i \le \left\lfloor\frac{n}{B}\right\rfloor$。则有 $$ \begin{aligned} \sum_{\substack{x\in R(n)\\x>B}}\sqrt x &= \sum_{i = 1}^{\left\lfloor\frac{n}{B}\right\rfloor} \sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\\ &= \Theta\left(\int_{1}^{\frac{n}{B}}\sqrt{\left\lfloor\frac{n}{i}\right\rfloor} \mathrm{d}x\right)\\ &=\Theta\left(\frac{n}{\sqrt B}\right)\\ \end{aligned} $$ ## 附录 B：PN 筛优化 定义：我们称只在 PN 的位置非 $0$ 的数论函数为 PN 函数。 ### 0. cmd 定理 > 设数论函数 $f$ 是 PN 函数，则 $f$ 关于 $n$ 的块筛只有 $O(n^{1 / 3})$ 个不同的值 **证明：** 考虑将 $x \in R(n)$ 从 $n^{2/3}$ 分为两部分： 1. 对于 $x \in R(n)$ 且 $x \le n^{2/3}$，根据 PN 个数的结论，这部分有 $O(n^{1/3})$ 个 $x$ 满足 $x \in \mathcal P$，即只有 $O(n^{1/3})$ 个非 $0$ 点值，自然前缀和最多只有 $O(n^{1/3})$ 种取值。 2. 对于 $x \in R(n)$ 且 $x > n^{2/3}$, 根据 $x = \lfloor n / i \rfloor > n^{2/3}$，可以推出 $i < n^{1/3}$，这部分最多有 $O(n^{1/3})$ 个 $x$。 相加得到 $f$ 关于 $n$ 的块筛只有 $O(n^{1/3})$ 种取值。 据此定理，我们可以认为 PN 函数关于 $n$ 的块筛是一个 $O\left(n^{1/3}\right)$ 的东西。 ### 1. 优化 回到文章 6.2 位置的部分： ![](https://cdn.luogu.com.cn/upload/image_hosting/1telyucw.png) 根据 Dirichlet 双曲法有： $$ S_{f}(n) = \sum_{i = 1}^{\lfloor \sqrt n \rfloor} h(i)S_g\left(\left\lfloor\frac{n}{i}\right\rfloor\right) + \sum_{i = 1}^{\lfloor \sqrt n \rfloor} g(i)S_h\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - S_h(\lfloor \sqrt n \rfloor)S_g(\lfloor \sqrt n \rfloor) $$ 第一项根据 PN 理论只有 $O\left(n^{1 / 4}\right)$ 个值，第二项根据 cmd 给出的定理，$h$ 关于 $n$ 的块筛可以简化成 $O\left(n^{1 / 3}\right)$ 信息量的东西。 也就是说，$S_f$ 单点求值可以做到 $O\left(n^{1 / 3}\right)$。 使用与杜教筛相同的阈值平衡方法，线性筛预处理 $f$ 的前 $B$ 项（设 $B \ge \sqrt n$），得到复杂度 $$ \begin{aligned} O\left(B + \sum_{x \in R(n), x > B} x^{1 / 3}\right) &= O\left(B + \int_{1}^{\frac{n}{B}} \left(\frac{n}{x}\right)^{1/3}\mathrm{d}x\right)\\ &= O\left(B + \frac{n}{B^{2 / 3}} \right) \end{aligned} $$ 这里运用了附录 A 的分析方法。 取 $B = \frac{n}{B^{2 / 3}}$，得到时间复杂度 $O\left(n^{3/5}\right)$。