在谈论新方法之前，先回顾一下前两篇（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)$．