感觉看东西的时候还是得自己手跟着推一遍比较好。
所以有了这篇博客。
OI-wiki。
Min_25 筛可以用来求某个积性函数 的前缀和，要求 是次数较少的多项式，且 可以快速求值。
一些符号的约定：
表示某个质数。
为艾佛森括号， 成立则 ，否则 。
，即
为质数是函数值为 ，否则是 。
表示从小到大的第 个质数，如 。特殊的，。
表示 的最小质因数，例如 。
，即 在 中所有质数上的点值之和。
，即 中，所有质因数都
的数的点值和。注意这里没有 。
，即
的前缀和，也是我们要求的东西。
可以发现 。
现在需要算出 ，考虑枚举一个数字最小的质因数为
， 的次数为 。
首先考虑
如何计算。他在这个式子中出现了两次，分别是 和 。
考虑第二部分，容易发现，调用的 一定有 。
对于前面这种情况，也能发现递归计算的过程中，一定只会访问到 形式的点。
也就是说
只有
这些点值是需要求的。
注意到我们要求
为项数不多的多项式，由于这部分只涉及质数的点值，那么我们不妨把 的每一项分开来算。
也就是说，这一部分，令
为完全积性函数，给定一个 ，我们需要对于每一个 求出 。
令 ，可以发现这等价于跑埃筛跑完 后， 内没被筛掉的
之和（前面的质数也算没有被筛掉）。
考虑对于一个合数一定有 。则对于
一定有 。
对于 的边界值，有 。
再来考虑如何计算 ，考虑按照埃筛的形式分开算贡献。
若 ，则 这一轮肯定什么都筛不掉，则有 ；
否则 ，考虑 筛掉了哪些数字，可以发现肯定是 的倍数。
那么筛掉的数字一定可以表示成 的形式，其中 。
这相当于若 被删掉了，一定有
在 之前没有被删掉。
也就是说这一轮筛掉了 。
但是我们的
是包含了所有质数的点值的，也就是说
都算在了里面。
所以这一部分还要减去 。
所以可以得到 。
考虑这部分的复杂度，我们对于一个 需要计算 。
考虑对于一个 ，我们只递推到
的 ，反正后面也不会变。
那么对于一个 ，他对复杂度贡献就是 。
对于 和 分开进行考虑，容易发现
的部分不占复杂度瓶颈。 这样我们就可以得出所有 的有效点值。
再来考虑 如何计算。 考虑直接按照递推式进行暴力递归，可证明复杂度为 。