如果还不会，或许也可以先从wc2018的原始课件或者 zzt blog（里面有一些小bug） 看一点基础知识．

从最基础的知识开始介绍吧，首先是 Dirichlet 双曲线法，对于数论函数 $f, g, h : \mathbb Z^+ \to R,f=g*h$，其中 $*$ 为 Dirichlet 卷积，$R$ 为交换环（并且有时假设，对于整数到 $R$ 的同态，较小的正整数的像可逆），那么有 $$ \sum _{n\leq x}f(n)=\sum _{n\leq x}\sum _{ab=n}g(a)h(b)=\sum _{a\leq {\sqrt {x}}}\sum _{b\leq {\frac {x}{a}}}g(a)h(b)+\sum _{b\leq {\sqrt {x}}}\sum _{a\leq {\frac {x}{b}}}g(a)h(b)-\sum _{a\leq {\sqrt {x}}}\sum _{b\leq {\sqrt {x}}}g(a)h(b) $$

从图像上理解，相当于是平面直角坐标系第一象限有一条双曲线 $\displaystyle y=\frac{n}{x}$ 也就是 $xy=n$，我们要对其下方（包括线上）的所有整点对 $(x, y)$，求 $g(x)h(y)$ 的和．我们对 $x \leq \sqrt n$ 的部分、$y \leq \sqrt n$ 的部分分别求和，再减去两者的公共部分．

也许会有人更熟悉“整除分块”的做法，它和上式只相差一个 Abel 变换，我想这个做法或许会方便操作，常数更小一些，不过无论如何二者能力是差不多的．

无论是用哪个式子，我们都需要知道 $g$ 和 $h$ 在一些位置上的前缀和（这里当然认为我们对 $g$ 和 $h$ 的单点值并没有更多了解）．这个位置的集合是我们非常熟悉的整除集合 $\displaystyle D_n=\left\{\left\lfloor\frac nm \right\rfloor \;\middle|\; m\in\mathbb Z^+ \right\}=\left\{0, 1, 2, \dots, \left\lfloor\sqrt n\right\rfloor-1, \left\lfloor\sqrt n\right\rfloor, \left\lfloor\frac n {\left\lfloor\sqrt n\right\rfloor}\right\rfloor, \left\lfloor\frac n {\left\lfloor\sqrt n\right\rfloor-1}\right\rfloor, \dots, \left\lfloor\frac n 2\right\rfloor, n\right\}$，这个集合的一些性质就不赘述了，可以参考 zzt blog．

可以看出来，这些位置的前缀和值是很重要的．我们记 $S_{n, f} : D_n \to R$ 表示 $f$ 在整除集合位置的前缀和函数，那么上文说明我们可以由 $S_{n, g}$ 和 $S_{n, h}$ 得到 $g*h$ 的前 $n$ 项和．我们对此并不满意：也许 $g*h$ 只是计算过程的一小步，我们希望可以得到 $S_{n, g*h}$．而这也不难做到，因为整除位置的整除集合是整除集合的子集，只需要直接对每个位置求一遍即可．经过计算容易得出这一过程的时间为 $\Theta(n^{3/4})$．

我们仍然不满意：这一过程还是稍微慢了一点．考虑对小于 $S$ 的位置暴力计算 Dirichlet 卷积求解，这样时间为 $O\left(S\log S+\sqrt n\sqrt{\frac nS}\right)$，取 $S=\Theta\left(\left(\frac{n}{\log n}\right)^{2/3}\right)$ 时为 $\Theta(n^{2/3}\log^{1/3} n)$．若数论函数为积性函数，可以通过记录 $S$ 以内函数的完整信息，增大空间开销使计算卷积的时间降为 $\Theta(S)$，此时取 $S=\Theta(n^{2/3})$ 时总时间为 $\Theta(n^{2/3})$．此外注意到对于 $f=g*h$，这种方法亦可用于已知 $S_{n, f}$ 和 $S_{n, g}$ 反推 $S_{n, h}$，由于一些历史原因，这种用法常常被称为“杜教筛”．

在一些特殊情况下（对，我的意思是下文会用到），两个函数的非零项密度为 $O(\log^{-1} n)$，此时时间为 $O\left(S\log S\log^{-2} n+\sqrt n\sqrt{\frac nS}\log^{-1} n\right)$，取 $S=\Theta(n^{2/3})$ 时总时间为 $\Theta(n^{2/3}\log^{-1}n)$．

现在我们考虑适用于一类积性函数的求和法，它要求函数在素数处的取值是关于素数的常数次多项式．

考虑积性函数的 Dirichlet 生成函数，作为积性函数，无非是意味着 $\displaystyle\mathrm{DGF}(f):=\sum_{n=1}^\infty f(n)n^{-s}=\prod_p\left(1+\sum_{k=1}^\infty f(p^k)(p^k)^{-s}\right)=:\prod_p\mathrm{DGF}(f_p)$．

可以花费 $O(\sqrt n\log_pn)$ 时间由 $S_{n, g}$ 得出 $S_{n, g*f_p}$ 或 $S_{n, g*f_p^{-1}}$．对于大于 $\sqrt n$ 的素数 $p$，我们无须关心其幂次位置的取值，于是考虑先求出关于这部分素数的多项式的前缀和．对多项式中不同的幂次 $k$，从 $id_k(n)=n^k$ 的前缀和 $S_{n, id_k}$ 开始，除去所有小于等于 $\sqrt n$ 的素数 $p$ 的贡献，再将其按照多项式进行组合（此时得到了 $\displaystyle\prod_{p>\sqrt n}\mathrm{DGF}(f_p)$ 对应的函数的前缀和），最后直接乘上其他素数的贡献即可．去除一些无用计算后，可以得到一个 $\Theta(n^{3/4}\log^{-1}n)$ 的算法，常被称为“洲阁筛”．其另有一个较小数据范围内速度较快的搜索变种，常被称为“min_25筛”．

此类方法还是不够令人满意．考虑按素数大小把这些因子分为 3 部分分别处理，即 $\displaystyle\mathrm{DGF}(f)=\left(\prod_{p\le n^{1/6}}\mathrm{DGF}(f_p)\right)\left(\prod_{n^{1/6}< p\le n^{1/2}}\mathrm{DGF}(f_p)\right)\left(\prod_{n^{1/2}< p}\mathrm{DGF}(f_p)\right)$．

先求出第二部分，注意到 $\displaystyle \prod_{n^{1/\alpha}< p\le n^{1/2}}\mathrm{DGF}(f_p)=\exp\sum_{n^{1/\alpha}< p\le n^{1/2}}\log\mathrm{DGF}(f_p)$，而 $\exp$ 内部式子最低项 $6$ 次方已超出 $n$，对答案无影响．于是只需要计算其 2、3、4、5 次方．注意到涉及的函数的非零项密度皆为 $O(\log^{-1} n)$（证明可参考zzt blog），所以计算这部分总时间为 $\Theta(n^{2/3}\log^{-1}n)$．

对于第一部分，考虑直接逐项乘到答案中，时间为 $\displaystyle \sum_{p\le n^{1/6}}O(\sqrt n\log_pn)=\int_1^{n^{1/6}}O(\sqrt n\log_pn)\log^{-1}p\,\mathrm{d}p=O(n^{2/3}\log^{-1}n)$．

对于第三部分，类似之前的做法，分解为从 $S_{n, id_k}$ 中去除小素数贡献的问题．可以用前面的方法直接算出小素数的前缀和函数，由于这部分的前缀和函数 $\sqrt n$ 以内几乎全为 0，所以用除法计算出来，再乘到答案上是很容易做到的，这部分时间也为 $\Theta(n^{2/3}\log^{-1}n)$．

以上算法大概就是简化后的zzt求和法了（）可以看出，这种求和法所需时间实际上只和做此类乘法的时间有关．

暂时还没有进一步研究，也没考虑怎么卡常，因为↓

写了一份代码，虽然过了模板题，但好像还有些没弄明白的bug（我家乘法不结合.png），其中282行~294行是与题目本身有关的内容，此外都是模板，感觉代码量还是有点大的．

现在修好了，拆解了一些过程，现在287行~299行是与题目本身有关的内容．

又修了一下，现在303行~315行是与题目本身有关的内容．

upd：仿佛整出来了个 $O(n^{2/3}\log^{-4/3}n)$ 甚至 $O(n^{2/3}\log^{-2}n)$ 的做法，还有更快的算 $\pi(n)$ 的做法，甚至让我想写点东西发出去，暂时就不公开了（x