一堆筛子

埃氏筛和线性筛就不多说了。

这里主要整理一堆能在亚线性复杂度下计算积性函数前缀和的筛法。

杜教筛

入门级筛子。比较难构造函数。

能 $O(n^{\frac{2}{3}})$ 求积性函数 $f(i)$ 的前缀和 $F(n) = \sum_{i = 1}^{n} f(i)$。同时也求出了所有 $F(\left\lfloor\frac{n}{k}\right\rfloor)$ 的值。

考虑设计一个前缀和能快速计算的积性函数 $g$ 使得 $f * g = h$ 的前缀和也能快速计算，则有。

$$\begin{aligned} \sum_{i = 1}^{n} (f * g)(i) & = \sum_{i = 1}^{n}\sum_{d|i}f\left(\frac{i}{d}\right)g(d) \\ & = \sum_{d = 1}^{n}g(d)\sum_{i = 1}^{\lfloor n / d \rfloor}f(i) \\ & = \sum_{d = 1}^{n}g(d)F\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\ & = F(n) + \sum_{d = 2}^{n}g(d)F\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\ \therefore F(n) & = \sum_{i = 1}^{n}(f * g)(i) - \sum_{d = 2}^{n}g(d)F\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{aligned}$$

整除分块求解即可。复杂度为 $O(n^{\frac{3}{4}})$。

预处理前 $O(n^{\frac{2}{3}})$ 个 $f$，将复杂度平衡至 $O(n^{\frac{2}{3}})$。

复杂度积分一下就能证了。

Min_25 筛

很强的筛子。

能 $O(n^{1-\epsilon})$ 求解一类积性函数 $f(i)$ 的前缀和 $F(n)$ 。但是只能求出单点的前缀和值。优点是跑得飞快。

其思想为先求出对于 $G(n) = \sum_{i = 1}^{n}f(i) \cdot [i\text{ is prime}]$ 的所有 $G\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$ 的值。然后再用其求 $F(n)$。

我们需要找到一个完全积性函数 $g$ 使得 $g$ 在质数处的取值与 $f$ 相同。那么可以得出 $G(n) = \sum_{i = 1}^{n}g(i) \cdot [i\text{ is prime}]$。

现在我们就拆分出了两个问题：

1. 对于一个完全积性函数 $g$，求出所有的 $G\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$。
2. 利用刚刚求得的所有 $G\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$，求出 $F(n)$。

假设我们已经做完了第一个问题，现在我们需要求解 $F(n)$。

考虑到所有合数的最小质因子一定 $\le \sqrt n$，因此我们可以对这个最小质因子做递归。具体来讲，设

$$F(i, j) = \sum_{k = 1}^{j} f(k) [k \text{ 的最小质因子} \ge p_i]$$

其中 $p_i$ 表示第 $i$ 个质数。$F(n)$ 就等于 $F(1, n) + f(1)$。考虑递归计算 $F(i, j)$，将所有可能的最小质因子单独拎出来：

$$\begin{aligned} F(i, j) & = \sum_{k \ge i, p_k^2 \le j} \sum_{p_k^{e + 1}\le j} f(p_k^{e + 1}) + f(p_k^e) \times F\left(k + 1, \left\lfloor\frac{j}{p_k^{e}}\right\rfloor\right) & \cdots (1)\\ & + G(j) - \sum_{k = 1}^{i - 1}f(p_k) & \cdots (2) \end{aligned}$$

$(1)$ 处，枚举当前满足条件的数的最小质因子 $p_k$ 及其幂次。

$(2)$ 处，将质数位置的函数值加入，但需要减去 $< p_i$ 的质数位置的函数值。

不需要记忆化。

这一步的复杂度被证明是 $O(n^{1 - \epsilon})$ 的，但是实测 $10^{10}$ 量级无压力。

下面问题是，如何求出所有的 $G\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$。

可以采用类似的定义，设

$$G(i, j) = \sum_{k = 1}^{j}g(k) \cdot [k\text{ is prime or }k \text{ 的最小质因子} > p_i]$$

这样 $G(t, n)$ 就是 $G(n)$ 的值（$t$ 表示 $\le \sqrt{n}$ 的素数个数）。

那么可以考虑用类似方法，把 $p_i$ 的影响筛掉来更新新的 $G$ 值。

$$\begin{aligned} G(i, j) & = G(i - 1, j) - \sum_{k = 1}^{j}g(k) \cdot [k\text{ is not prime and } k \text{ 的最小质因子} = p_i] \\ & = G(i - 1, j) - G\left(i - 1, \left\lfloor\frac{j}{p_i}\right\rfloor\right)\cdot g(p_i) + \left(\sum_{k = 1}^{i - 1}g(p_k)\right) \cdot g(p_i) \end{aligned}$$

其中，$G\left(i - 1, \left\lfloor\frac{j}{p_i}\right\rfloor\right)$ 代表了所有质数 $p_1, p_2, \ldots, p_{i - 1}$ 以及一切最小质因子 $\ge p_i$ 的数。我们希望减去一切最小质因子 $\ge p_i$ 的数乘上 $p_i$ 的函数值，也就是所有最小质因子就是 $p_i$ 的情况下的函数值。而直接减去 $G\left(i - 1, \left\lfloor\frac{j}{p_i}\right\rfloor\right) \cdot g(p_i)$ 后多减掉了所有 $p_1p_i, p_2p_i, \ldots, p_{i - 1}p_i$ 这些位置的函数值，因此需要加回来。

需要预处理 $\sum_{j = 1}^{i}g(p_j)$。

这一步骤的复杂度被证明是 $O\left(\frac{n^{\frac{3}{4}}}{\log n}\right)$ 的。

Powerful Number 筛

留坑待填。