筛法

· · 个人记录

以下令 P 表示全体质数集合。

一、狄利克雷生成函数

二、杜教筛

三、Powerful Number 筛

四、Min_25 筛

若无特殊说明，p 的取值范围为 P。

令 \mathrm{lpf}(n) 表示 n 的最小质因子，特别地，\mathrm{lpf}(1) = 1。

Min_25 筛也可以求积性函数 f 前缀和，其适用范围极广，只需要满足 f(p) 为低次多项式或可以快速求值，f(p ^ c) 可以快速求值。

Min_25 筛将 f 的前缀和分成了求质数处的和与合数处的和。其过程分为两部分。

首先构造一个完全积性函数 f'，满足 f'(p) = f(p)。

第一部分

这一部分主要用来处理出 f 质数处的和，由于构造 f'(p) = f(p)，所以可以转而求 f' 质数处的和。

令 p_k 表示第 k 个质数。

设 g(n, j) 表示筛了前 j 个质数，剩下数的 f' 的和，即 \displaystyle \sum_{i = 2} ^ n f'(i) [i \in P \lor \mathrm{lpf}(i) > j]。

则有 \displaystyle g(n, j) = \begin{cases} g(n, j - 1) \qquad {p_j}^2 > n \\ g(n, j - 1) - f'(p_j) \cdot (g(\lfloor\frac{n}{p_j}\rfloor, j - 1) - g(p_{j - 1}, j - 1)) \qquad \mathrm{otherwise} \end{cases}

当 {p_j}^2 > n 时，所有合数已经筛完了；否则筛去最小质因子为 p_j 的合数，其中需要减去 g(p_{j-1},j-1)，因为这些数的最小质因子不是 p_j。

注意到只需要 g(\lfloor\frac{n}{t}\rfloor, j) 与 g(p_j, j) 处的取值，将 j 这维滚存后，空间复杂度降为 \Theta(\sqrt n)，并且 j 也只需要枚举 \Theta(\sqrt n) 范围内的质数。

剩下部分直接做，需要注意的是对于一种 $\lfloor\frac{n}{t}\rfloor$ 的取值，只需要枚举到 $\Theta\left(\sqrt{\lfloor\frac{n}{t}\rfloor}\right)$ 范围内的质数。 分析一下时间复杂度，所有 $\lfloor\frac{n}{t}\rfloor$ 的取值可以考虑根号分治。 对于 $t\le \sqrt n$，有 $$\Theta\left(\sum_{i=1}^{\sqrt n} \dfrac{\sqrt{\dfrac{n}{i}}}{\log n}\right) = \Theta\left(\dfrac{\sqrt n}{\log n} \int_1^{\sqrt n} x^{-\frac12} \mathrm{d}x\right) = \Theta\left(\dfrac{n^{\frac34}}{\log n}\right)$$ 对于 $t>\sqrt n$，有 $$\Theta\left(\sum_{i=1}^{\sqrt n} \dfrac{\sqrt i}{\log i}\right) = \Theta\left(\sum_{i=1}^{\sqrt n} \dfrac{\sqrt n}{\log n}\right) = \Theta\left(\dfrac{n^{\frac34}}{\log n}\right)$$ 设 $s = \log i$，$h(s)=\dfrac{{\sqrt 2}^{s}}{s}$，则 $h'(s)=\dfrac{{\sqrt{2}}^s \cdot (\ln{\sqrt 2}\cdot s - 1)}{s^2}$，当 $s\ge 1$ 时，明显 $h'(s)>0$，则 $h(s)$ 在 $[1,+\infty)$ 为增函数，可以将 $\dfrac{\sqrt i}{\log i}$ 缩放为 $\dfrac{\sqrt{n}}{\log n}$。 所以这部分总体复杂度 $\Theta\left(\frac{n^{\frac34}}{\log n}\right)$。 ### 第二部分 设 $\displaystyle S(n,j)=\sum_{i=2}^n f(i)\cdot[\mathrm{lpf}(i)>p_j]$，则答案为 $S(n,0)+f(1)$。 对于 $S(n,j)$ 首先考虑质数部分，即为 $g(n,n)-g(p_j,j)$。 对于合数部分，考虑枚举其最小质因子： $$\sum_{k>j}\sum_{e=1}^{{p_k}^e\le n}f({p_k}^e)\cdot \left(S\left(\lfloor\frac{n}{{p_k}^e}\rfloor,k\right)+[e>1]\right)$$ 这个 $[e>1]$ 是由于 $S$ 中 $1$ 是不算进去的，所以要加一个 $f({p_k}^e)$，当 $e=1$ 时是由于质数已经算过了。 值得注意的是，这部分可以不需要记忆化，时间复杂度也是对的。 这部分时间复杂度的分析过于复杂，具体可参考朱震霆 2018 年集训队论文《一些特殊的数论函数求和问题》。 总时间复杂度 $\Theta\left(\frac{n^{\frac34}}{\log n}\right)$，常数极小。 ### 求积性函数的块筛 其实 Min_25 筛也能求积性函数的块筛（于是就吊打杜教筛了）。