0%

min25筛

min25 筛能够求解积性函数的前缀和。其时间复杂度为 $O(\frac{n^{\frac{3}{4}}}{\log n})$,空间复杂度为 $O(\sqrt n)$。

原理

首先,min25 筛对于每个 $x = \lfloor\frac{n}{i} \rfloor$,能够求出 $\sum_{i=1}^x [i \in P] i^k$ 的值。

先通过线性筛可以得到 $\sqrt n$ 以内的所有质数 $p_i$ 以及它们的前缀 $k$ 次方和 $sum_i$。

定义 $g(n, i) = \sum_{j=1}^n [j \in P or pr_j > p_i] j^k$,其中 $pr_j$ 表示 $j$ 的最小质因子。$g(n, i)$ 表示的就是埃筛进行第 $i$ 轮后尚未被筛去的数的 $k$ 次方和。那么所求答案即为 $g(n, cnt)$,$cnt$ 表示 $\sqrt n$ 以内质数的个数。

考虑如何通过 $g(n, i - 1)$ 求出 $g(n, i)$。

若 $p_i^2 >n$,则埃筛第 $i$ 轮不会筛去任何数,有 $g(n, i) = g(n, i - 1)$。

若 $p_i^2 \leq n$,有 $g(n, i) = g(n, i - 1) - p_i^k (g(\lfloor \frac{n}{p_i}\rfloor, i - 1) - sum_{i-1})$。由于 $p_i^2 \leq n$,所以有 $\lfloor\frac{n}{p_i}\rfloor > p_i$,因此 $\lfloor\frac{n}{p_i}\rfloor$ 以内最小质因数大于等于 $p_i$ 的数的 $k$ 次方和为 $g(\lfloor \frac{n}{p_i}\rfloor, i - 1) - sum_{i-1}$。

复杂度为 $O(\frac{n^{\frac{3}{4}}}{\log n})$。

接下来,考虑如何求 $\sum_{i=1}^n f(i)$。

代码