「Min25 筛」学习笔记

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

感谢 chd 哥哥让我学会 Min25 筛!(@Trisolaris

筛啥用的?

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

记号

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

怎么筛?

假设我们已经算出了所有 FF,可以发现答案就是 F1(n)+f(1)=F1(n)+1F_1(n) + f(1) = F_1(n) + 1

求 F

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

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

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

求 f 在质数处的值

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

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

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

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

复杂度?

并不会证明,由论文可得求 FkF_k 的复杂度为 Θ(n1ϵ)\Theta(n^{1-\epsilon})(第一种方法)。
FPF_{\mathbb P} 的复杂度为 (第二种方法的复杂度也长这样)。

一些提示

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

例题 - LibreOJ 6053.简单的函数

注意到质数除了 22 都是奇数,故 f(p)=p1+2[p=2]f(p) = p - 1 + 2[p=2]

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

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

arknights