定义
- 积性函数：本文的所有函数都是积性函数。
- 前缀和：函数 $f(x)$ 的前缀和为 $F(x) = \sum_{i = 1} ^ x f(i)$。
- 卷积：$f \ast g = h$ 表示数论函数 $f, g$ 的 $\text{Dirichlet}$ 卷积。
思路
如果我们需要求一个积性函数 $f(x)$ 的前缀和 $F(x)$，最简单的想法就是直接线性筛出所有的 $f(x)$ 然后求和，这种朴素做法的复杂度为 $\mathcal O(n)$，只能承受 $10 ^ 7$ 级别的数据，一旦数据规模变大就力不从心了。
考虑找到一个积性函数 $g(x)$，设 $f$ 和 $g$ 的 $\text{Dirichlet}$ 卷积为 $h$，即 $f \ast g = h$，并且 $g, h$ 的前缀和可以在非线性复杂度内求出（即 $\mathcal O(1)$ 或 $\mathcal O(\log n)$），我们就可以愉快地推式子啦！注意：对于所有积性函数 $f$ 都有 $f(1) = 1$。
$$ \begin{align*} F(n) & = \sum_{i = 1} ^ n f(i) \\ & = \sum_{i= 1} ^ n \left(h(i) - \sum_{d \mid i, d \ne 1} g(d) \cdot f\left(\frac{i}{d}\right)\right) \\ & = H(n) - \sum_{i = 1} ^ n \sum_{d \mid i, d \ne 1} g(d) \cdot f\left(\frac{i}{d}\right) \\ & = H(n) - \sum_{i = 2} ^ n g(i) \sum_{j = 1} ^ {\left\lfloor\frac{n}{i}\right\rfloor} f(j) \\ & = H(n) - \sum_{i = 2} ^ n g(i) \cdot F\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\ \end{align*} $$
发现 $H(n)$ 和 $g(i)$ 都可以快速计算，产生了一个子问题 $F\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$，显然可以数论分块解决，可以直接对其递归求解并记忆化。
直接这样做的复杂度为：
$$ T(n) = \sum_{i = 1} ^ {\sqrt n} T(i) + T\left(\left\lfloor\frac{n}{i}\right\rfloor\right) $$
我们考虑预处理前 $p$ 个 $f(x)$ 的值，线性筛预处理的复杂度为 $\mathcal O(p)$，则递归复杂度变为：
$$ T(n) = \sum_{i = 1} ^ {\left\lfloor\frac{n}{p}\right\rfloor} \sqrt{\frac{n}{i}} \approx \int_{0} ^ {\frac{n}{p}} \sqrt{\frac{n}{x}} \mathbb{dx} = \sqrt n \int_{0} ^ {\frac{n}{p}} x ^ {-\frac{1}{2}} \mathbb{dx} = \mathcal O\left(\frac{n}{\sqrt p}\right) $$
发现当 $p = n ^ {\frac{2}{3}}$ 时复杂度最优，为 $\mathcal O\left(n ^ {\frac{2}{3}}\right)$。
问题形式
$\varphi(i)$
$$ f = \varphi, g = 1, h = n $$
$\mu(i)$
$$ f = \mu, g = 1, h = \varepsilon $$
$i \cdot \varphi(i)$
$$ f = \text{ID}\cdot \mu, g = \text{ID}, h = n ^ 2 $$