min_25 筛

· · 个人记录

学习笔记。

只追求遇到的时候能够快速写出来。

min_25 的复杂度依赖于这个式子：

\sum_{p\in\text{prime},p\le\sqrt n}[\ge p^2\text{ 的块筛个数}]=O\left(\frac{n^{3/4}}{\ln n}\right)

min_25 可以求解某积性函数 f 块筛处的前缀和，条件：

min_25 使用如下过程求解 f 的块筛前缀和：

第一部分：

令 G(n,a) 表示 [1,n] 的数里，埃筛筛完前 a 个质数后没被筛掉的数的 g 值的和，具体地，包含以下三种数：

那么我们有如下转移式：

G(n,a)=G(n,a-1)-\sum_{i=1}^{c-1}g(p_a^i)\left(G\left(\left\lfloor\frac{n}{p_a^i}\right\rfloor,a\right)-[前\ a\ 个质数的\ g\ 值和]\right)-g(p_a^c)+g(p_a)

其中 c 为最大的非负整数使得 p_a^c\le n

初值为 G(n,0)=\sum_{i=1}^ng(i)，最后得到 G(n,\pi(\sqrt n))=\sum_{1\le p\le n,p \in\text{prime}}g(p)

由于 p_a\le\sqrt n，所以我们可以预先线性筛出来前 \sqrt n 个位置的 g 值，这样就可以 O(1) 回答质数处的前缀和

直接写上面的转移式即可，注意到只有 c\ge2 的位置才有意义，所以我们可以只枚举 \ge p_a^2 的块筛，那么复杂度由最开始的式子，是 O(n^{3/4}/\ln n) 的

第二部分：

令 F(n,a) 表示 [1,n] 的数里，埃筛筛完前 a 个质数后没被筛掉的数的 f 值之和

那么我们有如下转移式：

F(n,a-1)=F(n,a)+\sum_{i=1}^{c-1}f(p_a^i)\left(F\left(\left\lfloor\frac{n}{p_a^i}\right\rfloor,a\right)-[前\ a\ 个质数的\ f\ 值和]\right)+f(p_a^c)-f(p_a)

其中 c 为最大的非负整数使得 p_a^c\le n

初值为 F(n,\pi(\sqrt n))=\sum_{1\le p\le n,p\in\text{prime}}f(p)=G(n,\pi(\sqrt n))，最后得到 F(n,0)=\sum_{i=1}^nf(i)

复杂度分析与上面类似。

实际上，如果求块筛内质数个数的话，可以直接用第一部分，递推式为：

G(n,a)=G(n,a-1)-\left(G\left(\left\lfloor\frac n{p_a}\right\rfloor,a-1\right)-a\right)