目录
- Min-25 筛
- 1 - 核心思想
- 2 - 大体过程
- 2.1 - 记号与约定
- 2.2 - Part 1：转化为求出 \(G(n)\)
- 2.3 - Part 2：求出 \(G(n)\)
- PN 筛
Min-25 筛
1 - 核心思想
使用一种类似于 dp 的方式，以及最小质因数 \(\le \sqrt n\) 的性质，来优化求积性函数前缀和的复杂度。
具体的，你需要有一积性函数 \(f\)。
2 - 大体过程
2.1 - 记号与约定
\(p_i\) 表示第 \(i\) 个质数。
\(h(x)\) 表示 \(x\) 的最小质因子。
\(\mathbb{P}\) 表示质数集。
给出 \(F_{k}(n)\) 的定义为：
\[F_{k}(n) = \sum_{x = 1}^n [h(x) \ge p_k] f(x)
\]
给出 \(G(n)\) 的定义为：
\[G(n) = \sum_{x = 1}^n [x \in \mathbb{P}] f(x)
\]
2.2 - Part 1：转化为求出 \(G(n)\)
考虑计算 \(F_{k}(n)\)，先把其分为两个部分，质数与合数，对于合数部分，枚举最小质因数，并将其全部除去：
\[\begin{aligned}
F_{k}(n) &= G(n) + \sum_{x = 1}^n [x \not \in \mathbb{P} \land h(x) \ge p_k] f(x) \\
&= G(n) + \sum_{p \in \mathbb{P}} \sum_{e \ge 1 \land p^e \le n} f(p^e) (F_{k + 1}(\lfloor \frac{n}{p^e} \rfloor) + [e > 1])
\end{aligned}
\]
可以证明复杂度为 \(O(n^{1 - \epsilon})\)，问题在于求出 \(G\) 的 \(O(\sqrt n)\) 个点值（只有形如 \(\lfloor \frac{n}{y} \rfloor\) 的 \(x\) 有用）。
2.3 - Part 2：求出 \(G(n)\)
参考一下筛法，可以设计 \(G_{k}(n)\) 定义为：
\[G_k(n) = \sum_{x = 1}^n [h(x) \ge p_k \lor h(x) \in \mathbb{P}]
\]
存在转移：
\[G_k(n) = G_{k - 1}(n) - [p_k^2 \le n]f'(p)(G_{k}(\lfloor \frac{n}{p} \rfloor) - G_{k}(p_{k - 1}))
\]
注意，此处 \(f'(p)\) 是与 \(f(p)\) 在质数处点值相同的完全积性函数。