min25 小记

min25 筛可以处理这样一类问题：求 $F(x)$ 的前缀和，其中 $F(x)$ 是积性函数，且可以表示成 $F(p) = p^a +p^b + ...$ 这样的形式，其中 $p$ 是质数。

如果 $F(p)$ 是多项式，我们把它们拆开分别算，然后加起来。

我们希望先求出其质数位置上的值，设 $g(i, j)$ 为 $[2, i]$ 中，删去了 $p_1$ 到 $p_j$ 的真倍数后的 $F(x)$ 的和，其中 $p_i$ 为第 $i$ 小的质数。

则有 $g(i, j) = g(i, j - 1) - [g(\lfloor\dfrac{i}{p_j}, j - 1\rfloor) - \text{sumf}(j - 1)]$，其中 $\text{sumf}(k) = \sum_{i = 1}^{k} f(p_i)$。

然后我们考虑求出合数位置上的值，我们枚举其最小质因子即可。

设 $h(i, j)$ 表示 $[2, i]$ 中，包含了最小质因子 $\geq p_j$ 的数和 $\geq p_j, \leq i$ 的全体质数的 $f()$ 的和。

则有 $h(x, y) = g(x, \infin) - \text{sumf}(y - 1) + \sum_{i = y}\sum_{k = 1}^{p_i^k \leq x} f(p_i^k)[h(\lfloor\dfrac{x}{p_i^k}\rfloor, i + 1) + [k \not= 1]]$。

最后答案即为 $h(x, 0) + f(1)$，递归计算即可。