筛法
min 25筛
考不到的知识增加了！
总括
开始之前，先明确它可以干啥
显然它是计算（不完全）积性函数前缀和的，时间 $O(\frac{n^{\frac{3}{4}}}{\log n})$ ，空间 $O(\sqrt{n})$ ，要求是目标积性函数在质数处的可以拆成完全积性函数计算（比如是多项式），且较好算
它的主要思想是利用合数的最小质因子 $\le \sqrt{n}$ ，把质数、合数分开，构造二元函数递推
我们约定：
$cnt$ 表示 $\le n$ 的质数的个数， $p_i$ 表示第 $i$ 个质数， $R(x)$ 表示 $x$ 的最小质因子， $F(x)$ 是一个积性函数，默认除法下取整
由于我不会证时间，所以不证了
Part 1
该部分，我们的目标是求：
$$
\sum_{i = 1}^{cnt} F(p_i)
$$
首先我们定义 $f(x)$ 为把 $x$ 当成质数处理时 $F(x)$ 的值，那么由我们上面的要求可知， $f$ 是完全积性函数（也可能是多个完全积性函数之和，如果是这样，就拆开分别筛），我们定义二元函数 $g$ ：
$$
g(n, j) = \sum_{i = 2}^n f(i)[i \in primes \vee R(i) > p_j]
$$
考虑递推 $g(n, j - 1) \to g(n, j)$ ，显然两者差别就是 $R(x) == p_j$ 的合数要踢出去，分讨：
- 若 $p_j^2 \ge n$ 那么不存在 $R(x) \ge p_j$ 的合数
- 否则，设要删掉的 $x = p_j * k$ ， $k$ 取遍所有 $\ge p_j$ 的质数和 $R(k) \ge p_j$ 的数，且要保证 $p_j * k \le n$ ，发现 $g(\frac{n}{p_j}, j - 1)$ 包含了这些所有数，但多了 $ < p_j$ 的质数，去掉即可
综上，递推式为：
$$
g(n, j) =
\begin{cases}
g(n, j - 1) & p_j^2 \ge n \\
g(n, j - 1) - f(p_j) * (g(\frac{n}{p_j}, j - 1) - \sum_{k = 1}^{j - 1} f(p_k)) & otherwise
\end{cases}
$$
（注意到我们把 $f(p_j)$ 提出来了，因为它是一个完全积性函数）
我们的目标就是 $g(n, nct)$ ，由此， part 1 结束
考虑空间，注意到第一维是 $\frac{n}{?}$ 的形式，它只有 $O(\sqrt{n})$ 种可能取值，而第二维可以滚动，所以空间是 $O(\sqrt{n})$ 的，注意 $g$ 的初始化问题
Part 2
我们现在有 $\sum_{i = 1}^{cnt} F(p_i)$ ，还有 $O(\sqrt{n})$ 个 $g(?, cnt)$ ，目标是求出 $F$ 的前缀和 $Ans = \sum_{i = 1}^n F(i)$
还是考虑构造二元函数，设：
$$
S(n, j) = \sum_{i = 2}^{n} F(i) [R(i) \ge p_j]
$$
考虑将 $S$ 的分成质数和合数，对于 $S(n, j)$ 质数部分显然就是 $g(n, cnt) - \sum_{i = 1}^{j - 1} F(p_i)$
合数部分，由于 $F$ 只保证是不完全积性函数，我们不仅要考虑质数，还要考虑次幂，我们枚举一个 $p_k$ 和它对应的指数 $e$ ，表示合数 $x$ 的最小质因数为 $p_k$ ，次幂是 $e$ ，那么类似设 $x = p_k^e * t$ ， $t$ 要满足 $R(t) > p_k$ 且 $p_k^e * t \le n$ ，那么就是 $S(\frac{n}{p_k^e}, k + 1)$ ……吗？我们发现如果 $t = p_k$ ，即 $x$ 本身就是 $p_k$ 的次幂，也要计算，所以加上 $F(p_k^{e + 1})$
综上，递推式为：
$$
S(n, j) = g(n, cnt) - \sum_{i = 1}^{j - 1} F(p_i) + \sum_{p_k}^{p_k^2 \le n} \sum_{e}^{p_k^{e + 1} \le n} F(p_k^e) \times S(\frac{n}{p_k^e}, k + 1) + F(p_k^{e + 1})
$$
递归的边界就是 $n = 1 \vee p_j > n$ 此时 $S(n, j) = 0$ ，据说根据某玄学定理，不需要记忆化
最后 $Ans = S(n, 1) + F(1)$
注意到枚举的上界很特别，是 $p_k^2 \le n$ 和 $p_k^{c + 1} \le n$ ，两者显然都是对的，我们发现由于递归起点是 $S(n, 1)$ ，且有第一个条件，所以 $\sum_{i = 1}^{j - 1} F(p_i)$ 这里不会用到 $> \sqrt{n}$ 的质数值，可以预处理出来
代码
题目直接给了 $F(p^k) = p^{2k} - p^k$ ，那显然拆成 $f_1(x^k) = x^{2k}, f_2(x^k) = x_k$ 也即 $f_1(x) = x^2, f_2(x) = x$
1 |
|