众所周知，min_25曾经使用过一种较为通用的对积性函数求前缀和的亚线性筛法，复杂度为 $O(\frac{n^{0.75}}{logn})$ ，而在去年的11.11日，min_25又在他的个人博客上更新了一种新的求解积性函数前缀和的亚线性筛法，该算法的复杂度优化至了 $O(n^{\frac{2}{3}})$ ，但由于其博客为日文并且有诸多“省略”的地方理解起来较为不容易，因此打算写这么篇文章较为详细地解读这个新做法（勉强算教程向吧）。

与老版min_25筛的对比：

首先最大的差异便是复杂度了。老版的min_25筛复杂度为 $O(\frac{n^{0.75}}{logn})$ ，这而这个新筛法复杂度为 $O(n^{\frac{2}{3}})$ ，但事实上常数较为巨大，所以在时间上其实并不是太占优势（也可能是我的姿势不太对）。

在大致的思路方面其实两者的差异不是很大，新版min_25筛主要是在原有基础上利用树状数组和一些数论知识进行了一些加速，大体思路还是比较相似的（后半部分的方法对步骤进行了切割，变得更加复杂了）。

就适用范围来说，两种min_25筛所适用的都是满足”在质数处表达式为多项式，在质数的高次幂处可以快速求值”的积性函数。事实上如果对其原理较为熟悉的话是可以略微扩大一些它的适用范围的，但就我个人而言，新版min_25筛较老版更难变通，也可能是还不够熟悉这种筛法的缘故。

比较振奋人心的是新版min_25筛对于所求的 $n$ 可以同时得到 $F(\frac{n}{i})\ \ \ ( i \in [1,n])$ 处的所有的值，其中 $F(x)$ 表示该积性函数在 $x$ 处的前缀和。据我所知老版min_25筛只能对 $n$ 单点处求值，或者牺牲一定的时间/空间复杂度来记忆化获得其他 $O(\sqrt{n})$ 个点处的值。

一些也许会有用的前置资料：

1. min_25本人的blog: Sum of Multiplicative Function
2. 朱震霆的国家集训队论文： 《一些特殊的数论函数求和问题》, 国家集训队2018论文集
3. 计算 $\pi(x)$ 的meissel-lehmer方法： Computing $\pi(x)$ : The Meissel, Lehmer, Lagarias, Miller, Odlyzko method
4. yyb的blog(不错的老版min_25筛教程)： min_25筛
5. 我的blog(老版min_25筛前半部分的解读)： 一种亚线性筛法的详细解读(min_25筛前置)

一些符号与记号：

（以下基本照搬自min_25的blog）

$\pi(n)$ : $n$ 以下质数的个数。

$p_k$ : 第 $k$ 个质数（比如 $p_1=2$ , $p_2=3$ …）

$lpf(n)$ : $n$ 的最小质因子。 规定 $lpf(1) = \infty$

$F_{prime}(n)$ : $\sum_{p=2}^{n}[p为质数]f(p)$

$F_{k}(n)$ : $\sum_{i=1}^{n}[lpf(i) \geq p_k]f(i)$

$V(f,n)$ : $\lbrace(i,f(i))|1 \leq i \leq \lfloor \sqrt{n} \rfloor \rbrace \cup \lbrace(\lfloor \frac{n}{i} \rfloor,f(\lfloor \frac{n}{i} \rfloor))|1 \leq i \leq \lfloor \sqrt{n} \rfloor \rbrace$ 即：$f$ 函数在 $n,\frac{n}{2},…,1$ 这 $O(\sqrt{n})$ 个点处的取值。

大致的流程：

1. $O(n^{\frac{2}{3}})$ 计算出 $V(F_{prime},n)$
2. 利用 $V(F_{prime},n)$ , $O(\frac{n^{\frac{2}{3}}}{logn})$ 计算出 $V(F_{\pi(\sqrt[3]{n})+1},n)$
3. 利用 $V(F_{\pi(\sqrt[3]{n})+1},n)$ , $O(n^{\frac{2}{3}})$ 计算出 $V(F_{\pi(\sqrt[6]{n})+1},n)$
4. 利用 $V(F_{\pi(\sqrt[6]{n})+1},n)$ , $O(\frac{n^{\frac{2}{3}}}{logn})$ 计算出 $V(F_{1},n)$

计算 $V(F_{prime},n)$ ：

事实上关于这个的计算在我的blog（前置资料的第五篇）中已经详细介绍过了做法，不过那篇文章中的做法是 $O(\frac{n^{0.75}}{logn})$ 的。稍后我们会利用在后面过程中使用到的思想结合树状数组来将其复杂度优化到 $O(n^{\frac{2}{3}})$ 。

计算 $V(F_{\pi(\sqrt[3]{n})+1},n)$ ：

记 $q = p_{\pi(\sqrt[3]{n})+1}$

那么 $\forall \ m$ ,有 $F_{\pi(\sqrt[3]{n})+1}(m) = \sum_{i=1}^{m}[lpf(i) \geq q]f(i)$ 。

因为 $lpf(i) \geq p_{\pi(\sqrt[3]{n})+1}$ ，故 $i$ 要么是不小于 $q$ 的质数，要么是不小于 $q$ 的两个质数的乘积，要么就是 $1$ 。

于是就有 $F_{\pi(\sqrt[3]{n})+1}(m)=1+(F_{prime}(m)-F_{prime}(q-1)) +\sum_{p=q}^{\lfloor \sqrt{m} \rfloor}[p为质数] (f(p^2)+f(p)(F_{prime}(\lfloor \frac{m}{p} \rfloor)-F_{prime}(p)))$

若 $m \in [q^2,n]$ 转移式如上。

若 $m \in [q,q^2)$ 那么有 $F_{\pi(\sqrt[3]{n})+1}(m) = 1+(F_{prime}(m)-F_{prime}(q-1))$

若 $m \in [1,q)$ ，那么显然有 $F_{\pi(\sqrt[3]{n})+1}(m) = 1$ 。

复杂度呢？

显而易见的是当 $m \in [1,q^2)$ 时，更新都是 $O(1)$ 的，而落在这个区间中的 $m$ 个数是 $O(\sqrt{n})$ 的。
当 $m \in [q^2,n]$ 时，每次更新进行的次数即为 $\pi(\sqrt{m})-\pi(q-1)$ ，而 $m$ 遍历 $\frac{n}{1},\frac{n}{2},…,\frac{n}{\sqrt[3]{n}}$ 故总的复杂度即为 $O(\sum_{i=1}^{\sqrt[3]{n}}\pi(\sqrt{n/i})+\sqrt{n}) = O(n^{2/3}/logn)$ 。

计算 $V(F_{\pi(\sqrt[6]{n})+1},n)$ ：

记 $v$ 为 $\lfloor \sqrt[3]{n} \rfloor$

考虑以 $k=\pi(\sqrt[3]{n}),\pi(\sqrt[3]{n})-1,…,\pi(\sqrt[6]{n})+1$ 的顺序依次计算 $V(F_k,n)$ ：

通过枚举 $F_k(m)$ 中计算的数所包含的 $p_k$ 的幂次即可知道，我们有： $F_k(m)=\sum_{e=0}f(p_{k}^e)\cdot F_{k+1}(m/p_{k}^{e})$

如果直接使用这个式子更新，那么我们将会得到一个复杂度为 $O(\sum_{\sqrt[6]{n}<p \leq \sqrt[3]{n}}(\sum_{i=1}^{\sqrt{n}}(log_{p}(n/i)+log_{p}(i))))=O(n^{5/6}/logn)$ 的算法。这是不可取的。但是我们可以将这个过程“切分”一下：对于形如 $\lfloor \frac{n}{i} \rfloor \ \ (1\leq i \leq v)$ 的数我们使用上面提到的式子来更新，而对于剩下的部分，我们考虑使用树状数组来维护。因为有 $F_{k}(m)=F_{k+1}(m)+\sum_{i=1}^{m}[lpf(i)==p_k]f(i)$ ，所以我们每次只需要使用 $[p_k,\frac{n}{v+1}]$ 中最小质数恰好为 $p_k$ 的数 $t$ 来更新落在 $[t,\frac{n}{v+1}]$ 中的所有 $m$ 所对应的 $F_{k}(m)$ 即可。这一步可以用树状数组的区间更新来高速完成。然后在下一次更新时，若更新形如 $\lfloor \frac{n}{i} \rfloor \ \ (1\leq i \leq v)$ 的数时调用到了树状数组上维护的这一部分，那么就可以用树状数组的单点查询来完成这一步。

复杂度呢？

根据min_25的blog，不大于 $\frac{n}{v+1}$ 并且满足 $lpf(m)>\sqrt[6]{n}$ 的 $m$ 的个数是 $O(\frac{n^{\frac{2}{3}}}{logn})$ 的（ https://en.wikipedia.org/wiki/Buchstab_function ），所以区间更新的次数是 $O(\frac{n^{\frac{2}{3}}}{logn})$ 的。

而在树状数组上单点查询的次数是 $O(\sum_{\sqrt[6]{n}<p \leq \sqrt[3]{n}}(\sum_{i=1}^{v}log_{p}(n/i)))=O(n^{1/3}/logn \cdot n^{1/3})=O(\frac{n^{\frac{2}{3}}}{logn})$ 的.

这两个操作都是 $log(n)$ 的复杂度，因此总的复杂度降为了 $O(n^{2/3})$ 。

计算 $V(F_{1},n)$ ：

这一步就十分简单了，使用之前的式子 $F_k(m)=\sum_{e=0}f(p_{k}^e)\cdot F_{k+1}(m/p_{k}^{e})$ 根据 $k=\pi(\sqrt[6]{n}),…,1$ 的顺序更新即可。总的复杂度即为 $O(\sum_{2\leq p\leq \sqrt[6]{n}}(\sum_{i=1}^{\sqrt{n}}(log_{p}(n/i)+log_{p}(i))))=O(n^{2/3}/logn)$ 。

补充：计算 $V(F_{prime},n)$ ：

其实有了上面 $V(F_{\pi(\sqrt[6]{n})+1},n)$ 的计算方法之后，可以用类似的思路结合我的blog中写的老版min_25筛的前置步骤来完成这一步。初始化时，将形如 $\frac{n}{i}$ 且满足 $\frac{n}{i} \in [1,\frac{n}{v+1}]$ 的这 $O(\sqrt{n})$ 个数初始化为“将每个数都视为质数时的结果”,然后在第 $k$ 次更新时对每个 $F_p(m)-=\sum_{i=1}^{m}[lpf(i)=p_k 且i不为质数]f(i)$ 。然后对于 $\frac{n}{i} \ \ i \in [1,v]$ 的值，使用老版min_25筛的前置所述的方法来更新，这在我的博文里有详细的讲解。总的复杂度分析方法同计算 $V(F_{\pi(\sqrt[6]{n})+1},n)$ 的部分。

综上，在 $O(n^{2/3})$ 时间复杂度，$O(\sqrt{n})$ 的空间复杂度内完成了 $V(F_1,n)$ 的计算，亦即我们要求的积性函数前缀和。

其他：

计算积性函数：
$$
f\left( x \right) =\left\lbrace \begin{array}{l}
1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\left( x=1\textrm{或}x=p^e,\textrm{其中}e>1,p\textrm{为质数} \right)\\
p+1\,\,\,\,\,\,\,\,\,\,\left( x=p,p\textrm{为质数} \right)
\end{array} \right.
$$

的前缀和：代码

代码风格比较差，见谅。

赏

谢谢你请我吃糖果

支付宝