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

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

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

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

上篇文章解释了可以通过改进乘法时间来改进求和时间，因此我们继续考察乘法时的贡献形状，每个位置会贡献到结果的哪个整除块。这大致是用形如 $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}$ 小的。不过时间有限先摸了