OI 数论中的上界估计与时间复杂度证明

预备

1 约数函数 ${\sigma }_z(n)$

约数函数（Divisor Function，也可称为除数函数、因数函数）是与 $n$ 的因子有关的一类函数，定义如下：

Definition 1 (约数函数) $${\sigma }_z(n)=\sum _{d\mid n}{d}^z$$

当 $z=0$ 时，${\sigma }_0(n)$ 被称为约数个数函数（number-of-divisors function），常被记为 $d(n)$ 或 $\tau (n)$. 当 $z=1$ 时，${\sigma }_1(n)$ 被称为约数和函数（sum-of-divisors function），常直接记为 $\sigma (n)$.

Example 1 估计 ${\sigma }_0(n)$ 的渐进上界.

也就是估计 $n$ 的因子的数量. 一个广为人知的上界是 $2\sqrt{n}$，因为 $n$ 的所有小于 $\sqrt{n}$ 的因子 $d$ 均与另一因子 $\frac{n}{d}$ 一一对应.

事实上进一步可以证明 ${\sigma }_0(n)\in o(n^{ϵ})\mathrm{\forall }ϵ>0$^[7] ，虽然这在 OI 中并不实用.

Example 2 估计 $\widehat{{\sigma }_0}(n)=\sum _{i=1}^n{\sigma }_0(i)$ 的渐进上界.

即估计 $1$ 到 $n$ 中所有数因子个数的和. 这是一个形式上鲜为人知但其应用广为人知的例子. 变换求和顺序，容易得到

$$\widehat{{\sigma }_0}(n)=\sum _{i=1}^n{\sigma }_0(i)=\sum _{i=1}^n\sum _{d\mid i}1=\sum _{d=1}^n\lfloor \frac{n}{d}\rfloor \le \sum _{d=1}^n\frac{n}{d}=nH(n)\in O(n\log n)$$

显然，这比 $O(n\sqrt{n})$ 的平凡估计好上不少. 本例的思路不仅是埃氏筛（Sieve of Eratosthenes）的理论基础，也在杜教筛、快速 Mobius 变换、$gcd$ 卷积^[8] 等处出现.

进一步利用此技巧和 $p$ - 级数的估计，我们甚至能在仔细研究 ${\sigma }_z(n)$ 前就得到其前缀和的渐进估计：

Example 3 估计 $\widehat{{\sigma }_z}(n)=\sum _{i=1}^n{\sigma }_z(i)$ 的渐进上界.

$$\begin{array}{rl}\widehat{{\sigma }_z}(n)& =\sum _{i=1}^n{\sigma }_z(i)=\sum _{i=1}^n\sum _{d\mid i}{d}^z=\sum _{d=1}^n{d}^z\lfloor \frac{n}{d}\rfloor \\ & \le n\sum _{d=1}^n{d}^{z-1}=n{P}_{1-z}(n)\in \{\begin{array}{ll}O(n^{z+1})& z>0\\ O(n\log n)& z=0\\ O(n)& z<0\end{array}\end{array}$$

遗憾的是，对此前缀和做差分并不能得到 ${\sigma }_z(n)$ 的优秀估计.

现在引入一个重要放缩技巧，其在后续估计中屡试不爽.

Proposition 1 $$\sum _{d\mid n}f(d)\le \sum _{i=1}^{n}f(\lfloor \frac{n}{i}\rfloor )$$

显然，右式比左式多算了 $i\nmid n$ 的项，因此命题是正确的. 但我们还可以做得更好：

Proposition 2 $$\sum _{d\mid n}f(d)\le \sum _{i=1}^{\sqrt{n}}f(i)+f(\lfloor \frac{n}{i}\rfloor )$$

$\sqrt{n}$ 分治. 我们其实已经在 Example 1 估计 ${\sigma }_0(n)$ 时用过此技巧了.

Example 4 估计 ${\sigma }_1(n)$ 的渐进上界.

用 Proposition 1： $${\sigma }_1(n)=\sum _{d\mid n}d\le \sum _{i=1}^n\lfloor \frac{n}{i}\rfloor \le nH(n)\in O(n\log n)$$

可以证明用 Proposition 2 不会得到更优的结果.

我们发现了一个有趣的事实：${\sigma }_1(n)$ 和 $\widehat{{\sigma }_0}(n)$ 的渐进上界均为 $O(n\log n)$.

Example 5 估计 ${\sigma }_z(n)$ 的渐进上界.

用 Proposition 2 和 $p$ - 级数的性质：

$$\begin{array}{rl}{\sigma }_z(n)& =\sum _{d\mid n}{d}^z\le \sum _{i=1}^{\sqrt{n}}{i}^z+{\lfloor \frac{n}{i}\rfloor }^z\\ & \le \{\begin{array}{lll}{\displaystyle 2\sum _{i=1}^{\sqrt{n}}{\lfloor \frac{n}{i}\rfloor }^z\le 2n^z\sum _{i=1}^{\sqrt{n}}{i}^{-z}}& =2n^z{P}_z(\sqrt{n})& z\ge 0\\ {\displaystyle 2\sum _{i=1}^{\sqrt{n}}{i}^z}& =2P_{-z}(\sqrt{n})& z<0\end{array}\\ \in & \{\begin{array}{ll}2n^{z}O(1)& z>1\\ 2nO(\log \sqrt{n})& z=1\\ 2n^{z}O(n^{\frac{1-z}{2}})& 0\le z<1\\ 2O(n^{\frac{1+z}{2}})& -1<z<0\\ 2O(\log \sqrt{n})& z=-1\\ 2O(1)& z<-1\end{array}=\{\begin{array}{ll}O(n^z)& z>1\\ O(n\log n)& z=1\\ O(n^{\frac{1+z}{2}})& -1<z<1\\ O(\log n)& z=-1\\ O(1)& z<-1\end{array}\end{array}$$

我们得到了一个相当优秀的渐进上界. 值得关注的是：

• 当 $z=0$ 时，${\sigma }_0(n)\in O(n^{\frac{1}{2}})$. 这与 Example 1 的结果一致.
• 当 $z=\frac{1}{2}$ 时，${\sigma }_{\frac{1}{2}}(n)\in O(n^{\frac{3}{4}})$，即 $\sum _{d\mid n}\sqrt{d}\in O(n^{\frac{3}{4}})$. 洛谷 P4980 Polya 定理模板题^[9] 的一种比较 trivial 的解法^[10] 的时间复杂度证明就来源于此. 我们之后还会在整除分块与杜教筛中见到它.

另外，如果只使用 Proposition 1 ，$-1<z<1$ 部分的渐进上界将只能估计至 $O(n)$. 因此 Proposition 2 是更为优越的.

约数函数更复杂的上限与渐进估计可参考 Wikipedia^[7].

2 整除分块

也被称为数论分块. 求 $$\sum _{i=1}^{n}f(i)g(\lfloor \frac{n}{i}\rfloor )$$ 我们按 $d=\lfloor \frac{n}{i}\rfloor$ 分块求和： $$\sum _{d}g(d)\sum _{\lfloor \frac{n}{i}\rfloor =d}f(i)$$ 可以证明，对一指定的 $d$，满足 $d=\lfloor \frac{n}{i}\rfloor$ 的 $i$ 取遍一连续区间，故若 $f$ 的前缀和能 $O(1)$ 求出，块数量 $\mathrm{\#}{\left\{\lfloor \frac{n}{i}\rfloor \right\}}_{i=1}^n$ 即该算法的时间复杂度. 注意到当 $i\le \sqrt{n}$ 时，$\lfloor \frac{n}{i}\rfloor$ 最多只有 $\lfloor \sqrt{n}\rfloor$ 种取值，而 $i\ge \sqrt{n}$ 时，$1\le \lfloor \frac{n}{i}\rfloor \le \sqrt{n}$ 表明其也最多只有 $\lfloor \sqrt{n}\rfloor$ 种取值. 因此整除分块的时间复杂度 $$T_1(n)=\mathrm{\#}{\left\{\lfloor \frac{n}{i}\rfloor \right\}}_{i=1}^n\le 2\sqrt{n}\in O(\sqrt{n})$$

方便起见，后文记 $D(n)={\left\{\lfloor \frac{n}{i}\rfloor \right\}}_{i=1}^n$.

3 杜教筛

杜教筛可以以低于线性的时间复杂度求解某些数论函数的前缀和. 其思路并不复杂. 设 $f$ 为一数论函数，我们希望快速求得其前缀和 $\hat{f}(n)=\sum _{i=1}^{n}f(i)$. 考虑数论函数 $g$ 和 $h=g\ast f$， $$h(n)=\sum _{d\mid n}g(d)f(\frac{n}{d})$$ 两端做前缀和得 $$\begin{array}{rl}\hat{h}(n)& =\sum _{i=1}^{n}h(i)\\ & =\sum _{i=1}^n\sum _{d\mid i}g(d)f(\frac{i}{d})\\ & =\sum _{d=1}^{n}g(d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i)\\ & =\sum _{d=1}^{n}g(d)\hat{f}(\lfloor \frac{n}{d}\rfloor )\\ & =g(1)\hat{f}(n)+\sum _{d=2}^{n}g(d)\hat{f}(\lfloor \frac{n}{d}\rfloor )\end{array}$$ 因此 $$\hat{f}(n)=\frac{1}{g(1)}(\hat{h}(n)-\sum _{d=2}^{n}g(d)\hat{f}(\lfloor \frac{n}{d}\rfloor ))$$

故若 $g$、$h$ 的前缀和可 $O(1)$ 算得，根据上式整除分块即可递归地计算出 $f$ 的前缀和.

下面分析算法的复杂度. 注意到 $$\lfloor \frac{\lfloor \frac{n}{i}\rfloor }{j}\rfloor =\lfloor \frac{n}{ij}\rfloor$$ 故单轮递归涉及到的自变量均可表示为 $d=\lfloor \frac{n}{i}\rfloor$ 的形式. 一个 $\hat{f}(d)$ 做整除分块耗时 $T_1(d)$，若采用记忆化递归，由上节分析，算法总时间复杂度为 $$\sum _{d\in D(n)}{T}_1(d)=T_2(n)\in O(n^{\frac{3}{4}})$$

但我们还可以做得更好——考虑先用 $O(K)$ 的时间复杂度线性筛出前 $K$ 个 $f(n)$ 并求前缀和，则递归求解时，$d\le K$ 的 $\hat{f}(d)$ 就无需再向下递归了. 为分析此类时间复杂度，对 Proposition 3 做最后一点扩展：

Proposition 4 $$\sum _{\begin{array}{c}d\mid n\\ d>K\end{array}}f(d)\le \sum _{\begin{array}{c}d\in D(n)\\ d>K\end{array}}f(d)\le \sum _{K<i\le \sqrt{n}}f(i)+\sum _{1\le i\le min\{\lfloor \frac{n}{K}\rfloor ,\sqrt{n}\}}f(\lfloor \frac{n}{i}\rfloor )$$

特别的，当 $K>\sqrt{n}$ 时，有

$$\sum _{\begin{array}{c}d\mid n\\ d>K\end{array}}f(d)\le \sum _{\begin{array}{c}d\in D(n)\\ d>K\end{array}}f(d)\le \sum _{1\le i\le \lfloor \frac{n}{K}\rfloor }f(\lfloor \frac{n}{i}\rfloor )$$

故用 Proposition 4 ，当 $K>\sqrt{n}$ 时，算法在递归部分的时间复杂度降低为

$$\begin{array}{rl}\sum _{\begin{array}{c}d\in D(n)\\ d>K\end{array}}{T}_1(d)& =\sum _{1\le i\le \lfloor \frac{n}{K}\rfloor }{T}_1(\lfloor \frac{n}{i}\rfloor )\\ & \le \sum _{1\le i\le \lfloor \frac{n}{K}\rfloor }C\sqrt{\frac{n}{i}}\\ & =C\sqrt{n}\sum _{1\le i\le \lfloor \frac{n}{K}\rfloor }{i}^{-\frac{1}{2}}\\ & =C\sqrt{n}{P}_{\frac{1}{2}}\left(\lfloor \frac{n}{K}\rfloor \right)\\ & \in \sqrt{n}O\left({\left(\frac{n}{K}\right)}^{\frac{1}{2}}\right)\\ & \subset O(n{K}^{-\frac{1}{2}})\end{array}$$

总时间复杂度为 $$O(K)+O(n{K}^{-\frac{1}{2}})$$

为最小化时间复杂度，取 $K=n^{\frac{2}{3}}$，得到最优时间复杂度 $O(n^{\frac{2}{3}})$.

这部分的时间复杂度证明主要参考了文章^[11].