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$ 块筛处的前缀和，条件：

• 存在一个容易求前缀和的积性函数 $g$ 在质数处点值与 $f(p)$ 相同

• $f(p^k),g(p^k)$ 可以快速求值

---

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

• 第一部分：从 $g$ 块筛前缀和，得到 $g$ 块筛处，质数位置前缀和，由于 $g(p)=f(p)$，也即 $f$ 块筛处，质数位置前缀和

• 第二部分，由 $f$ 块筛处，质数位置前缀和，得到 $f$ 块筛处前缀和

---

第一部分：

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

• $1$

• $n$ 以内的质数

• $n$ 以内的，最小质因子 $>p_a$ 的合数

那么我们有如下转移式：

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