在谈论新方法之前，先回顾一下前两篇（OI中常用数论函数求和法的简化陈述，OI 积性函数求和传统做法的最后一块拼图）所说的我们现有的做法框架与工具

对数论函数考虑 $n$ 的所有整除位置的前缀和．称大于 $\sqrt n$ 的素数为大素数，那么

1. 对于积性函数，所有整除位置的前缀和可以拆成小素数贡献和大素数贡献两部分乘起来．大素数贡献只有素数处贡献所以可以任意进行线性组合．给大素数贡献乘上小素数贡献或从完整贡献中除去小素数贡献得到大素数贡献都能做到 $O(\sqrt n \log n)$ 时间．

2. 小素数贡献 $\prod_{p \le \sqrt n} f_p$ 可以转为 $\exp \sum_{p \le \sqrt n} \log f_p$ 做到快速计算．

3. 可以用 $O(\sqrt n \log n)$ 时间改变每个素数的二次及以上的贡献（或许可以简称 powerful 贡献）．这意味着我们计算过程可以先不考虑如何处理 powerful 贡献（一般是让它保持为 0，至少要知道当前的贡献具体是什么，这样才能在之后进行处理），最后再将它修正为想要的值，在传统方法中有常数优化和简化实现的作用．

4. 可以用 $O(\sqrt n s \log^{-2} s)$ 时间（一些情况下使用数据结构可以更快，参见前文）取消或附加 $s$ 以下小素数的贡献．在传统方法中，很多操作都可以使用这一方法“稀疏化”给时间优化若干个 $\log$ 因子．

传统做法框架即为先得到大素数贡献，再乘上小素数贡献得到答案．而大素数贡献则可由若干易于快速计算前缀和的积性函数的大素数贡献线性组合而来．

可以看出，其他部分都可以很快完成，关键在于第 2 点是否能进一步优化．

这时候就可以使用 https://www.cnblogs.com/zkyJuruo/p/17544928.html 和今年国家集训队论文中提到的思路，使用形式幂级数近似进行优化．计算 exp 的具体思路参见 IOI2024 中国国家集训队论文集《关于积性函数求和问题的一些进展》的 4.1 部分（其他部分对于积性函数求和的问题都不重要），或者也可以参考下文给出的一篇文章（但他们没发现计算的是 exp，并且能改造成通用的做法），这里不再重复．以下将主要讨论做法的优化和简化以及复杂度分析．

首先，这个做法使用形式幂级数的连乘进行近似，而连乘的计算方法一般是使用 exp．注意到在形式幂级数近似的背景下，我们常常能直接计算出 $\sqrt n$ 以下的结果从而得到幂级数的前一半，因此在使用 Newton 法时可以直接快进到最后一轮迭代．（如果不熟悉 Newton 法的优化可参考 关于优化形式幂级数计算的 Newton 法的常数．）于是令转换后需要计算 exp 的形式幂级数为 $f$，$f$ 的前一半为 $f_0$，$\exp f$ 的前一半为 $g_0$，$1/\exp f$ 的前一半为 $h_0$，则最终结果为 $g_0 - g_0(\smallint{(h_0({g_0}'-g_0f_0')+(f_0-f)')})$．仅需实现多项式乘法即可完成这一部分的任务．

随后需要修正近似导致的误差．由于我们没有 powerful 贡献，需要修正的数自然也无平方因子，因此最大素因子数无条件为最大不同素因子数，即 $O(\log n / \log \log n)$．于是仅需考虑长 $O\left(\frac{n}{S}\log n / \log \log n\right)$ 区间范围内的数．当然，实际实现时可以直接计算出考虑各种因素后的最大素因子数量．修误差时也可以考虑因子数量的影响，如果当前数因子数太小，不能使结果产生误差，当然就不用考虑它的因子了．

这是进行以上优化后的一个参考实现，可以看出目前的实现在 OI 可接受的范围内仍然比传统方法要慢，若想使它适合跑 OI 范围的问题的话仍然有待改进．

在很长一段时间里，我一直不知如何分析以上做法时间复杂度．直到我发现这篇 Computing $\pi(N)$: An elementary approach in $\tilde O(\sqrt N)$ time，才得知类似的方法在 2022 年底就已经被发现了（尽管文中的方法还不够好），并且里面给出了复杂度分析的思路．那么接下来让我们来进行一下复杂度分析．

首先我们需要 Shiu 在 A Brun-Titschmarsh theorem for multiplicative functions 中给出的一个关键引理，如下

引理 1. 对于积性函数 $f$，若存在 $c, d$ 使得所有 $\ell \ge 1$ 和素数 $p$ 满足 $f(p^\ell) \le c \cdot \ell^d$，那么对任意 $\epsilon > 0, N^\epsilon < S < N$，有 $$ \sum_{n=N}^{N+S} f(n)=O\left(\frac{S}{\log N}\exp\left(\sum_{p \le 2N}\frac{f(p)}{p}\right)\right) $$

然后我们对几个数论函数使用这个引理

引理 2. 令 $d_{> L}(n)$ 为 $n$ 的所有素因子大于 $L$ 的因子数量，那么对任意 $\epsilon > 0, N^\epsilon < S < N$，有 $$ \sum_{n=N}^{N+S} d_{> L}(n)=O\left(S\log N/\log L\right) $$

证明. 使用引理 1. 各项条件显然满足，于是 $$ \begin{aligned} \sum_{n=N}^{N+S} d_{> L}(n)&=O\left(\frac{S}{\log N}\exp\left(\sum_{p \le L}\frac{1}{p}+\sum_{L < p \le 2N}\frac{2}{p}\right)\right) \\ &=O\left(\frac{S}{\log N}\exp\left(\log \log L + 2 (\log \log (2N) - \log \log L) + O(1)\right)\right) \\ &=O\left(S \log N / \log L \right) \end{aligned} $$

引理 3. 对任意 $\epsilon > 0, N^\epsilon < S < N$，区间 $[N, N+S]$ 所有不同素因子数 $\omega(n) \ge k$ 的数，无平方因子的因子数量 $2^{\omega(n)}$ 的和 $$ \sum_{n=N}^{N+S} [\omega(n) \ge k] 2^{\omega(n)}=O\left(\frac{S\log^3 N}{2^k}\right) $$

证明. $$ \begin{aligned} \sum_{n=N}^{N+S} [\omega(n) \ge k] 2^{\omega(n)}&\le\sum_{n=N}^{N+S} 2^{2\omega(n)-k} \\ &=2^{-k}\sum_{n=N}^{N+S} 4^{\omega(n)} \\ &=O\left(2^{-k}\frac{S}{\log N}\exp\left(\sum_{p \le 2N}\frac{4}{p}\right)\right) \\ &=O\left(2^{-k}\frac{S}{\log N}\exp\left(4\log \log N + O(1)\right)\right) \\ &=O\left(\frac{S\log^3 N}{2^k}\right) \end{aligned} $$

这些引理准备好了，接下来就可以开始分析了．将修正误差时考虑的数分为 2 类，一类的不同素因子数 $\omega(n) < 3 \log_2 \log_2 n$，离 $n$ 距离超过 $O\left(\frac{n}{S}3 \log \log n\right)$ 的这些数因子数不够造成误差，剩下在这个范围内的数根据引理 2 枚举因子数量不超过 $O\left(\frac{n}{S}\log n\log\log n/\log L\right)$．而对于 $\omega(n) \ge 3 \log_2 \log_2 n$ 的数，根据引理 3 枚举因子数量不超过 $O\left(\frac{n}{S}\right)$．因此修误差总共枚举的因子数不超过 $O\left(\frac{n}{S}\log n\log\log n/\log L\right)$．

如此一来，整个做法使用了处理 powerful 贡献、（没有使用数据结构的）处理 $L$ 以下素数的贡献、多项式乘法、区间筛、枚举无平方因子的因子修误差，时间复杂度为 $O\left(\sqrt n \log n + \sqrt n L \log^{-2} L + S \log^2 n + \frac{n}{S} \log n + \frac{n}{S}\log n\log\log n/\log L\right)$，取 $S = O\left(\sqrt{\frac{n}{\log n}}\right), L = O(\log n)$ 即可得时间复杂度为 $O\left(\sqrt n \log^{3/2} n\right)$．

上面链接的文中还给出了优化区间筛部分复杂度的方法，能把这部分复杂度降低到 $O(\frac{n}{S} (\log\log n)^2)$．但我最近想了一段时间没有想到如何优化枚举因子修误差的部分，一大困难是不会修误差做法特有的一些数论对象数量估计，感觉可能最多只能少一点点 $\log \log n$ 因子．若是想要继续降低 $\log n$ 因子似乎较为困难，或许需要些不一样的方法．

upd：发现原本的 $O\left(\sqrt n \log n \log \log n\right)$ 算素数幂和的方法有问题，这部分删了，回头看看能不能修，不过那篇论文里的素数计数方法仍然可以用上述方法优化到 $O\left(\sqrt n \log n \log \log n\right)$．

这篇文章不幸地被我鸽到了今天，但这些东西最终总是得以某种形式记录下来的，至少赶制一下而不是让它被封存在群聊消息的垃圾堆里。

今天要谈的是，上次文章最后提到但是没有详细谈论的。

这篇文章可能不是很详细，有需要的话我之后有时间会补充更多细节。

本文内容没有经过仔细论证，如果有问题我全责。

上篇文章解释了可以通过改进乘法时间来改进求和时间，因此我们继续考察乘法时的贡献形状，每个位置会贡献到结果的哪个整除块。这大致是用形如 $xy=n$ 的曲线划出很多带状区域，要计算的是每个区域中的贡献。考虑到曲线在 $x=y$ 两侧分别渐进 $x$ 轴和 $y$ 轴，因此可以考虑分别计算两侧的贡献。如对 $x=y$ 以下的部分，我们一行一行进行计算，在较小的部分会有很多曲线挤在一起，较大的部分则会有很长的一整块贡献。我们使用类似整除分块的计算方法（并且跳过0贡献的部分）即可，这种计算方法来自乘法本身的结构，而不是人为的分块，这种“某种意义上最优”的乘法时间复杂度为 $O(n^{2/3}\log^{-4/3}n)$（大致分析就是考虑非0项密度，分较小和较大两部分分别计算代价）（而没有稀疏性的一般情况下是 $O(n^{2/3})$）。这也暗示了传统方法难以继续优化了，要再改进可能得用一些一次函数近似或者仍未发现的方法。

附加/取消小素数贡献的部分也可以进一步优化。首先和上面一样可以利用稀疏性跳过贡献为 0 的部分，最常做的贡献是从小值到大值，而小值有稀疏性，因此可以暂时改为维护段内和而非前缀和，这样可以用 $O(\sqrt n s \log^{-2} s)$ 时间取消或附加 $s$ 以下小素数的贡献。

使用之前的框架，换上以上更快的做法，即可得到时间复杂度为 $O(n^{2/3}\log^{-4/3}n)$ 的做法。这是一个这个做法的实现。这个实现中通过单独处理powerful部分的贡献做了进一步的简化/常数优化。

附加/取消小素数贡献一般用上面的方法就足够了，不过我们还可以再进一步，由于贡献主要为小值的一段贡献到大值单点，我们对小值维护前缀和而大值维护段内和，然后用数据结构维护贡献。有 $O(\sqrt{n s} \log^{-3/2} s)$ 次操作是小值贡献到大值，而有 $O(\sqrt n \log s)$ 是小值到小值或大值到大值，相当于是进行 $O(\sqrt{n s} \log^{-3/2} s)$ 次单点操作，$O(\sqrt n \log s)$ 次区间操作。于是 $s = \Theta(n^c)$ 时可以用常数层分块数据结构优化到 $O(\sqrt{n s} \log^{-3/2} n)$，相当于乘法中计算一行贡献的时间。结合之前的方法甚至能完全避免进行 exp 与乘法的计算。或者可以理解为本来附加这些贡献要用 exp 和乘法整体一起计算，现在改用数据结构动态维护了。

可以看出，$s$ 以下素数贡献为 $0$ 最显著的效果是使得积性函数非 $0$ 值密度为 $O(1/\log s)$，这一操作过程本身也是利用了这一性质进行优化。在传统方法中，很多操作都可以利用无小素数贡献导致的稀疏性（或在本身没有稀疏性但有积性时，使用这一方法进行“稀疏化”）给时间优化若干个 $\log$ 因子。

当时所有人都知道这个下界需要一个多项式乘法或者一次近似之类的东西来打破（学术界有用分块一次近似的方法 $O(n^{3/5})$ 算 $\mu$ 前缀和的论文），$n^{1/3}$ 处附近与 $n^{1/3}$ 处附近的乘法是整个计算的瓶颈（具体到上面这个做法，最慢的地方是在 $n^{1/3}\log^{1/3}n$ 附近），曲线之间基本刚好差 1，贡献类似一个被扭曲的多项式乘法。大家都知道这东西必然不比多项式乘法容易，但直到遥远的以后大家才发现有个非常简单的解决方案。

另一方面，注意到 $\mathrm{id}_j * \mathrm{id}_k$ 这个积性函数求和单点可以用 $O(n^{1/3} \log^3 n)$ 时间计算（参见2018年论文集zzt的《一些特殊的数论函数求和问题》的第4部分，注意到其实有 $\sum_{x=1}^{n}\sigma(x)\sigma(x + 1)=O(n\log^2n)$（展开 $\sigma(x)$，将枚举因子的求和移到外面。某天我在群里说原文放缩明显放太大了，然后 EntropyIncreaser 立刻指出了正确的分析方法），段数实际比文章给出的结果要少，再在每段使用“万能欧几里得”$O(\log n)$ 时间计算）。于是对于素数处取值为多项式的数论函数乘法，$pq$ 处值可以使用若干 $id_j * id_k$ 的线性组合凑出系数，于是大素数分界点可以降低到 $n^{1/3}$，避免了之前做法在 $n^{1/3}\log^{1/3}n$ 处的瓶颈，从而优化到 $O(n^{2/3}\log^{-3/2}n)$。

一些情况下，我们过程中不需要关心所有整除位置的值。如求素数幂和，在算出大素数贡献后，无需像积性函数一样乘上小素数贡献得到答案，只需要加上小素数数量即可。由于不需要再附加小素数，并且只关心积性函数在 $n$ 处的值，需维护的大位置前缀和密度同样仅为 $1/\log n$，这样即可将时间降到 $O(n^{2/3}\log^{-2}n)$。（这种方法可能可以优化到更小的空间，待我有时间了研究一下）

如果利用上面的近似方法，我们还可以做得更好。我们取消掉 $\mathrm{id}_k$ 和 $\mathrm{id}_k^2$ 中 $n^{1/4}$ 以下素数的贡献，并计算出取消了 $n^{1/4}$ 以下素数贡献后的 $\mathrm{id}_k^3$ 在 $n$ 处的前缀和。由于取消掉了 $n^{1/4}$ 以下素数的贡献，非 $0$ 位置素因子数最多为 3，于是我们可以线性组合消去大部分非素数的贡献，只需再修正 $p^2$ 和 $p^3$ 位置的贡献即可。如此可以得到 $O(n^{5/8} \log^{-2} n)$ 的做法。

然而，半年前我们有了 更快的组合做法，至少是在渐进意义上。其实际时间与上述做法的交点暂时未知。如上所说，早年大家就知道这东西不比多项式乘法容易，但从来没有人想过直接这样近似嗯做的误差能够修好。这种做法这么好使想都不敢想，震撼我一整年。

当然，这个做法也可以用先取消小素数贡献的方法优化。取消掉小于 $\log n$ 的小素数的贡献后，$\exp$ 的幂次可以截断到 $\log n / \log \log n$，因此我们其实有 $O(n^{1/2}\log^3 n / \log \log n)$ 的做法。

upd：2024年国家队论文有进一步的优化，同时也可以结合我做法的框架进一步简化，同时还有单轮倍增计算多项式exp、dfs修误差时剪枝等可以优化的地方，但目前在 OI 范围内仍然比传统方法慢，是否能进一步优化仍然有待研究。upd：写在了这里

有兴趣的话我可以之后写写学术界对此的研究，一个显著特点就是为了进行实际计算，尽管时间可能大一些，但空间都是远比 $n^{1/2}$ 小的。不过时间有限先摸了

如果还不会，或许也可以先从wc2018的原始课件或者 zzt blog（里面有一些小bug） 看一点基础知识．（upd：csdn 现在需要登录并关注才能看了）

upd：本文于 2024.01.30 凌晨 review 了一遍，干掉了很多坏的表述（感觉后半基本是重写了），原来写的感觉自己都要看不懂了！!1

从最基础的知识开始介绍吧，首先是 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(f) : D_n \to R$ 表示 $f$ 在整除集合位置的前缀和函数（符号中省去 $n$，因为我们这里考虑的 $n$ 总是固定的），那么上文说明我们可以由 $S(g)$ 和 $S(h)$ 得到 $g*h$ 的前 $n$ 项和．我们对此并不满意：也许 $g*h$ 只是计算过程的一小步，我们希望可以得到 $S(g*h)$．而这也不难做到，因为整除位置的整除集合是整除集合的子集，只需要直接对每个位置求一遍即可．经过计算容易得出这一过程的时间为 $\Theta(n^{3/4})$．

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

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

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

为了方便以下不区分积性函数和它的 Dirichlet 生成函数，$f(x)$ 意思仍然和上文一样，在本文语境下对 Dirichlet 级数进行求值显然没有任何意义．

用 $f_p$ 表示对 $f$ 仅保留 $p$ 的幂处的值，其余值设为 0，积性函数无非是意味着 $\displaystyle 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 f_p$．

我们希望对一个中间结果附加或取消 $f_p$ 的贡献，即由 $S(g)$ 得出 $S(g*f_p)$ 或 $S(g / f_p)$，这可以用 $O(\sqrt n\log_pn)$ 时间做到（对每个点的前缀和考虑如何贡献到它即可）．

（比较重要的情况为仅有 $p$ 处有贡献，而更高幂次处没有贡献．直接计算乘法显然是 $O(\sqrt n)$ 时间，而除法自然是按乘法的过程倒推回去．）

（另一个常见的情况是对完全积性函数附加/取消贡献，完全积性意味着 $f_p$ 的逆很简单，为 $1-f_p(p)p^{-s}$，此时将乘或除以 $f_p$ 变为除以或乘 $f_p^{-1}$ 即可更轻松地进行操作．）

仅考虑大于 $\sqrt n$ 的素数的贡献 $\displaystyle S\left(\prod_{p>n^{1/2}}f_p\right)$（以下简称“大素数贡献”），此时任何 $pq$ 都会大于 $n$，因此只会在素数处非 0，于是可以将任意素数处取值为多项式的积性函数的大素数贡献拆解为 $id_k$ 的大素数贡献的线性组合．

于是我们有了个做法：先通过对 $id_k$ 取消小素数贡献得到大素数贡献，然后组合出想要求的积性函数的大素数贡献，然后再附加上小素数贡献即可．这样我们就得到了一个 $\displaystyle \sum_{p\le n^{1/2}}O(\sqrt n\log_pn)=\int_1^{n^{1/2}}O(\sqrt n\log_pn)\log^{-1}p\,\mathrm{d}p=O(n\log^{-1}n)$ 的做法．

但我们真的只能做这么好吗？考虑取消贡献时从小到大取消，附加贡献则相反，从大到小附加．当我们准备取消素数 $p$ 的贡献时，$p^2$ 以下只有 $1$ 和大于等于 $p$ 的素数处有值，这意味着这部分的值可以快速获取而无需进行维护，我们只需要考虑大于等于 $p^2$ 的部分受到了什么样的影响即可．既然如此，我们不如取消贡献时仍然保留素数处的值，这样 $p^2$ 以下的前缀和都无需再进行维护．以 $n^{1/4}$ 为分界，分别计算可得 $\displaystyle \sum_{p\le n^{1/4}}O(\sqrt n\log_pn)+\sum_{n^{1/4}< p\le n^{1/2}}O\left(\frac{n}{p^2}\log_pn\right)=O(n^{3/4}\log^{-1}n)$

（上面的分析里有很多 $\log_pn$ 项似乎使得分析变得不方便，其实容易发现它根本不影响结果．可以选定足够小的 $c$ 在 $n^c$ 处进行分段，小于等于 $n^c$ 的部分很小，可以直接放缩成 $\log n$ 而不影响最终结果，大于 $n^c$ 的部分 $\log_pn$ 为常数．亦可直接在算法中用 $O(n^{1/2}\log n)$ 时间（upd：我这部分写得比较晚，这里的 $O(n^{1/2}\log n)$ 的方法是注意到仅 powerful 部分非 0 的积性函数非常稀疏，直接枚举每个非 0 值，使用我下一篇 blog 所说“最优”乘法的做法中一行的贡献方法暴力算贡献即可）修改 powerful 部分的贡献（比如我们要从积性函数 $f$ 得到积性函数 $g$，若它们的素数处值都相同，则 $g/f$ 为仅有 powerful 部分非 0 的积性函数，可暴力算出 $S(g/f)$ 乘到 $S(f)$ 上．利用 powerful number 的想法，我最早能找到 利用powerful number求积性函数前缀和 - fjzzq2002（如果仅求单点值的话，修性质较好的 powerful 贡献其实能做到 $O(n^{2/5} \log^{-8/5} n)$，方法基本是下一篇 blog 思路的延续），从而根本无需乘上 $\log_pn$）

这种做法常被称为“洲阁筛”．其另有一个较小数据范围内速度较快的搜索变种，常被称为“min_25筛”，根据 OEIS 所说，“min_25筛”的复杂度大致为 $n \exp\left(-(1 + o(1))\sqrt{\log n \log \log n}\right)$．

这样的方法还是不够令人满意．我们以 $O(n\log^{-1}n)$ 的做法为框架，考虑再将小素数按 $n^{1/6}$ 分为 2 类，不妨重新将 $p\le n^{1/6}$ 称为小素数，而将 $n^{1/6}< p\le n^{1/2}$ 称为中素数．

假使我们已经得到中素数的贡献 $\displaystyle S\left(\prod_{n^{1/6}< p\le n^{1/2}}f_p\right)$，然后直接将小素数贡献附加上去得到 $\displaystyle S\left(\prod_{p\le n^{1/2}}f_p\right)$，仿照上文分析易知附加小素数需 $O(n^{2/3}\log^{-1}n)$ 时间．而计算出小中素数单独的贡献后，从整体中取消贡献或与大素数贡献合并仅需 $O(n^{1/2}\log n)$ 时间．

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

以上算法大概就是简化后的zzt求和法了（）可以看出，通过调整小素数分类位置选取，可以进一步减少附加小素数的开销，而对计算中素数贡献的开销只有常数影响，除非将乘法时间降到 $\tilde O(n^{1/2})$．因此这种求和法所需时间实际上只和做乘法的时间有关．

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

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

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

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

upd：仿佛整出来了个 $O(n^{2/3}\log^{-4/3}n)$ 甚至 $O(n^{2/3}\log^{-2}n)$（upd：很久之后发现算错了，其实是 $O(n^{2/3}\log^{-3/2}n)$）的做法，还有更快的算 $\pi(n)$ 的做法（x）（upd：被我鸽了 2.5 年后写在了这里）

The cruel world...

在一切之前，把微小的工作尽可能做好吧。

该来的，总是要来的呢……

过了这么久，总算是下决心写一个较完整的介绍了啊……

这次要写的是，top tree 相关的东西究竟是什么，为什么说这东西实际上远强于 OI 中所流传的版本。

阅读更多……

凛冽的风……

仿佛要将这最后的，仅剩的，微不足道的，存在的意义，剥下呢……

大概今年 6 月的时候用后缀树推了一遍 Blumer 的后缀自动机构造算法，还考虑了一些其他相关的东西，不过并没想清楚……前不久听说北大集训出了这样的题，于是就把这个坑填上了……这次要写的是，写起来要考虑的东西略多的维护双向加字符的字符串的隐式后缀树，就当是给大家的圣诞节礼物吧。

6 月时写过用后缀树解释 Blumer 的后缀自动机构造算法，但可能不是很能看，所以就没有发出来了。

阅读更多……

非常抱歉……又让您失望了呢……

2 年过去了……我还是一点进步都没有……一次大型比赛都没打好……

真的会有那样一天……像您那样强吗？……

想写的那些东西果然还是太麻烦了……根本写不动……就写一些没什么意思的东西吧……关于优化求形式幂级数的牛顿法的常数。

虽然写得很糟糕但还算是能看的，所以就发出来了。

2020年疫情期间更新了一些东西

阅读更多……

//为防止误解，还是声明一下。。下面标引用的东西是照着某著名slide写的（

阅读更多……

emmmmmm...前段时间学校要写个科技小论文。。。

也不知怎么的，莫名就写了个奇怪东西，反正不是论文。

大概就是找来一堆论文（主要也就那几个），翻译拼凑一番（参考文献都不需要找了）。。。

把（一部分）动态树数据结构（ET-trees、ST-trees和top trees）粗略介绍了一遍。

顺便说一下，真正的top trees使用姿势可能在11页。。。对应的模板题大概是QTREE系列加上link和cut。。。

（Alstrup et al.: "Top trees generalize balanced binary search trees！"）

（模板题可能还有link cut 找类似重心的东西。。。）

阅读更多……