「Min25 筛」学习笔记

Min25 太神仙了！
据说这个筛法的复杂度是 或 $\Theta(n^{1 - \epsilon})$ 的。（别问我 $\epsilon$ 是啥，问就不知道
本质上其实是扩展埃筛。

感谢 chd 哥哥让我学会 Min25 筛！（@Trisolaris

筛啥用的？

积性函数前缀和，不然用着干啥（
要求被筛的函数 $f$ 在质数 $p$ 处的值 $f(p)$ 的值为一个关于 $p$ 的低次多项式，在 $p^c$ 处的值 $f(p^c)$ 可以快速计算。

记号

• $\mathbb P$ 表示全体质数的集合。
• 本文一般默认 $p \in \mathbb P$。
• $p_k$ 为第 $k$ 小的质数。特别地，$p_0 = 1$。
• $\text{lpf}(n)$ 表示 $n$ 的最小质因子（即 Least Prime Factor
• $F_{\mathbb P} = \sum\limits_{2 \le p \le n} f(p)$
• $F_k = \sum\limits_{i = 2}^n [p_k \le \text{lpf}(i)] f(i)$

怎么筛？

假设我们已经算出了所有 $F$，可以发现答案就是 $F_1(n) + f(1) = F_1(n) + 1$。

求 F

枚举最小质因子及其质数可得

嗯，最后一个等号有点迷。
注意到若 $p_i^c \le n < p_i^{c+1}$，显然有 ，故 。

假设已经求得了所有 $F_{\mathbb P}$，现在理论上有两种方法计算 $F$，然鹅我只会第一种即直接递归（第二种就是洲阁筛

求 f 在质数处的值

根据递推式可以发现实际上需要用到的 $F_{\mathbb P}$ 只有形如 的 $O(\sqrt n)$ 处。
根据条件，$f(p)$ 可以写作 $\sum a_i p^i$。
故我们可以分别讨论每一项的贡献。

设 $G_{k,x}(n) = \sum\limits_{i = 1}^n [p_k < \text{lpf}(i) \lor i \in \mathbb P]i^x$。
熟悉埃筛的话，你会发现这相当于是埃筛筛了 $k$ 轮后剩下的数的 $x$ 次方之和。

最后我们想要的实际上就是 $G_{cnt,x}(n)$，其中 $cnt$ 表示 $|\{p : p \le \sqrt n\}|$。
因为一个合数的最小质因子肯定不会超过其开方。

考虑转移。
对于 $n < p_k^2$，并没有筛掉新的数，故直接转移即可。
对于 $p_k^2 \le n$，筛掉的数显然有质因子 $p_k$，故减去 。
然鹅我们筛掉的应该是 $\text{lpf}(m) = p_k$ 的 $m$，故要考虑 $\text{lpf}(m) < p_k$ 的 $m$ 的贡献。
实际上就是加回 $p_k^x G_{k - 1,x}(p_{k - 1})$。
综上所述，有

复杂度？

并不会证明，由论文可得求 $F_k$ 的复杂度为 $\Theta(n^{1-\epsilon})$（第一种方法）。
求 $F_{\mathbb P}$ 的复杂度为 （第二种方法的复杂度也长这样）。

一些提示

很多东西可以直接欧拉筛预处理，至于是啥，自己想想。

例题 - LibreOJ 6053.简单的函数

注意到质数除了 $2$ 都是奇数，故 $f(p) = p - 1 + 2[p=2]$。

于是有 $G_{0,0}(n) = -n + 1,G_{0,1} = \dfrac{(n+2)(n-1)}2$。
然后对 $2$ 讨论一下即可。

代码见 https://www.alpha1022.me/articles/loj-6053.htm