Min_25 筛

定义

从此种筛法的思想方法来说，其又被称为「Extended Eratosthenes Sieve」。

由于其由 Min_25 发明并最早开始使用，故称「Min_25 筛」。

性质

其可以在 或 的时间复杂度下解决一类 积性函数 的前缀和问题。

要求： 是一个关于 的项数较少的多项式或可以快速求值； 可以快速求值。

记号

• 如无特别说明，本节中所有记为 的变量的取值集合均为全体质数。
• ，即 为质数时其值为 ，否则为 。
• ：全体质数中第 小的质数（如：）。特别地，令 。
• ，即 的最小质因数。特别地， 时，其值为 。

解释

观察 的定义，可以发现答案即为 。

---

考虑如何求出 。通过枚举每个 的最小质因子及其次数可以得到递推式：

最后一步推导基于这样一个事实：对于满足 的 ，有 ，故 。
其边界值即为 。

假设现在已经求出了所有的 ，那么有两种方式可以求出所有的 ：

1. 直接按照递推式计算。
2. 从大到小枚举 转移，仅当 时转移增加值不为零，故按照递推式后缀和优化即可。

---

现在考虑如何计算 。
观察求 的过程，容易发现 有且仅有 这 处的点值是有用的。
一般情况下， 是一个关于 的低次多项式，可以表示为 。
那么对于每个 ，其对 的贡献即为 。
分开考虑每个 的贡献，问题就转变为了：给定 ，对所有的 ，求 。

Notice： 是完全积性函数！

于是设 ，即埃筛第 轮筛完后剩下的数的 值之和。
对于一个合数 ，必定有 ，则 ，故只需筛到 即可。
考虑 的边界值，显然为 。（还记得吗？特别约定了 ）
对于转移，考虑埃筛的过程，分开讨论每部分的贡献，有：

1. 对于 的部分， 值不变，即 。
2. 对于 的部分，被筛掉的数必有质因子 ，即 。
3. 对于第二部分，由于 ，故会有 的 被减去。这部分应当加回来，即 。

则有：

---

复杂度分析

对于 的计算，其第一种方法的时间复杂度被证明为 （见 zzt 集训队论文 2.3）；
对于第二种方法，其本质即为洲阁筛的第二部分，在洲阁论文中也有提及（6.5.4），其时间复杂度被证明为 。

对于 的计算，事实上，其实现与洲阁筛第一部分是相同的。
考虑对于每个 ，只有在枚举满足 的 转移时会对时间复杂度产生贡献，则时间复杂度可估计为：

对于空间复杂度，可以发现不论是 还是 ，其均只在 处取有效点值，共 个，仅记录有效值即可将空间复杂度优化至 。

首先，通过一次数论分块可以得到所有的有效值，用一个大小为 的数组 记录。对于有效值 ，记 为 在 中的下标，易得：对于所有有效值 ，。

然后分开考虑小于等于 的有效值和大于 的有效值：对于小于等于 的有效值 ，用一个数组 记录其 ，即 ；对于大于 的有效值 ，用一个数组 记录 ，由于 过大所以借助 记录 ，即 。

这样，就可以使用两个大小为 的数组记录所有有效值的 并 查询。在计算 或 时，使用有效值的 代替有效值作为下标，即可将空间复杂度优化至 。

过程

对于 的计算，我们实现时一般选择实现难度较低的第一种方法，其在数据规模较小时往往比第二种方法的表现要好；

对于 的计算，直接按递推式实现即可。

对于 ，可以用线性筛预处理出 来替代 递推式中的 。
相应地， 递推式中的 也可以用此方法预处理。

用 Extended Eratosthenes Sieve 求 积性函数 的前缀和时，应当明确以下几点：

• 如何快速（一般是线性时间复杂度）筛出前 个 值；
• 的多项式表示；
• 如何快速求出 。

明确上述几点之后按顺序实现以下几部分即可：

1. 筛出 内的质数与前 个 值；
2. 对 多项式表示中的每一项筛出对应的 ，合并得到 的所有 个有用点值；
3. 按照 的递推式实现递归，求出 。

例题

求莫比乌斯函数的前缀和

求 。

易知 。则 。
直接筛即可得到 的所有 个所需点值。

求欧拉函数的前缀和

求 。

首先易知 。
对于 的一次项 ，有 ；
对于 的常数项 ，有 。
筛两次加起来即可得到 的所有 个所需点值。

「LOJ #6053」简单的函数

给定 ：

易知 。则按照筛 的方法筛，对 讨论一下即可。
此处给出一种 C++ 实现：