min_25 筛

学习笔记。

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

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

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

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

第一部分：

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

那么我们有如下转移式：

其中 $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$ 值之和

那么我们有如下转移式：

其中 $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)$

复杂度分析与上面类似。

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