如何轻松得到7log做法？

· · 算法·理论

可能是解析数论学习笔记，也可能不是。起源是之前在牛客某场口胡了一个 \sum d(i)^3 的做法，然后发现是 7log ，非常开心。

1.1 \sum d(i)^k 的量级分析

考虑 S_k(n)=\sum\limits_{i\le n}d(i)^k。由于 d(n)^k 是积性函数，其 Dirichlet 级数为 F_k(s)=\sum\limits_{n\ge 1}\frac{d(n)^k}{n^s}=\prod_p\sum\limits_{a\ge 0}(a+1)^kp^{-as}. 对于一个素数 p，令 z=p^{-s}，我们有 \sum\limits_{a\ge0}(a+1)^kz^a=1+2^kz+O(z^2)，而 (1-z)^{-2^k}=1+2^kz+O(z^2)，因此可以提出 \zeta(s)^{2^k}。

令 m=2^k，写成 F_k(s)=\zeta(s)^mG_k(s),G_k(s)=\prod_p(1-p^{-s})^m\sum\limits_{a\ge0}(a+1)^kp^{-as}. 我们注意到 G_k(s) 中每个素数对应的项为 1+O(p^{-2\operatorname{Re}s})，因此其在 \operatorname{Re}s>\frac12 绝对收敛，特别地 G_k(1) 存在且非零，所以 F_k(s) 在 s=1 处恰有 2^k 阶极点。

由 Dirichlet 级数在 s=1 的 r 阶极点对应部分和的 n\log^{r-1}n 主项，可以得到 \sum\limits_{i\le n}d(i)^k=nP_{2^k-1}(\ln n)+O_{k,\epsilon}\left(n^{1-\frac1{2^k}+\epsilon}\right), 其中 P_{2^k-1} 为 2^k-1 次多项式。进一步有 \sum\limits_{i\le n}d(i)^k\sim C_kn(\ln n)^{2^k-1},C_k=\frac1{(2^k-1)!}\prod_p\left(1-\frac1p\right)^{2^k}\sum\limits_{a\ge0}\frac{(a+1)^k}{p^a}. 因此其主次量级分别为 n\log^{2^k-1}n 和 n\log^{2^k-2}n。

特别地，k=2 时有 \sum\limits_{a\ge0}(a+1)^2z^a=\frac{1+z}{(1-z)^3}，因此 F_2(s)=\frac{\zeta(s)^4}{\zeta(2s)}, 从而 \sum\limits_{i\le n}d(i)^2\sim\frac1{\pi^2}n(\ln n)^3.

1.2 另一个常用的量级分析

考虑 \sum\limits_{i\le n}d_k(i)=\sum\limits_{i\le n}\#\{(i_1,i_2,\dots,i_k)\mid i_1\mid i_2\mid\dots\mid i_k=i\}.

由于 d_k=\underbrace{1*1*\dots*1}_{k\text{ 次}}，其 Dirichlet 级数为 \sum\limits_{n\ge1}\frac{d_k(n)}{n^s}=\zeta(s)^k. 因此其在 s=1 处有 k 阶极点，可以得到 \sum\limits_{i\le n}d_k(i)=nP_{k-1}(\ln n)+O_{k,\epsilon}\left(n^{1-\frac1k+\epsilon}\right), 其中 P_{k-1} 为 k-1 次多项式。

由 \zeta(s)=\frac1{s-1}+\gamma+O(s-1)，有 \zeta(s)^k=\frac1{(s-1)^k}+\frac{k\gamma}{(s-1)^{k-1}}+\dots，结合 Perron 公式中的 \frac{n^s}{s} 可以得到前两项 \sum\limits_{i\le n}d_k(i)=\frac{n(\ln n)^{k-1}}{(k-1)!}+\frac{k\gamma-1}{(k-2)!}n(\ln n)^{k-2}+O_k(n(\ln n)^{k-3}). 因此其主次量级分别为 n\log^{k-1}n 和 n\log^{k-2}n。

1.3 常数分析

令人愉快的是，这些渐进量级的常数都小于 1 ，因此会跑的很快 —— 吗？

考虑一般的 Dirichlet 级数 F(s)=\zeta(s)^rG(s)，其中 G(s) 在 s=1 附近解析且 G(1)\neq 0。令 w=s-1,L=\ln n，由 \zeta(1+w)=\frac1w+\gamma+O(w) 可以得到 F(1+w)=\frac{G(1)}{w^r}+\frac{G'(1)+r\gamma G(1)}{w^{r-1}}+O(w^{-r+2}). Perron 公式中还需要乘上 \frac{n^s}{s}=n\frac{e^{Lw}}{1+w}，而 \frac{e^{Lw}}{1+w}=e^{Lw}(1-w+O(w^2)), 因此 w^{r-1} 的系数为 \frac{L^{r-1}}{(r-1)!}-\frac{L^{r-2}}{(r-2)!}+O(L^{r-3})，w^{r-2} 的系数为 \frac{L^{r-2}}{(r-2)!}+O(L^{r-3})。取 w=0 处留数，可以得到 \sum_{i\le n}f(i)=n\left(\frac{G(1)}{(r-1)!}L^{r-1}+\frac{G'(1)+(r\gamma-1)G(1)}{(r-2)!}L^{r-2}+O(L^{r-3})\right). 因此如果记前两项为 n(A\log^{r-1}n+B\log^{r-2}n)，则 A=\frac{G(1)}{(r-1)!},\qquad B=\frac{G'(1)+(r\gamma-1)G(1)}{(r-2)!}, 从而有 \frac BA=(r-1)\left(r\gamma-1+\frac{G'(1)}{G(1)}\right).

先考虑 1.2，此时 F(s)=\zeta(s)^k，即 r=k,G(s)=1，所以 A=\frac1{(k-1)!},\qquad B=\frac{k\gamma-1}{(k-2)!}, 也就得到 \sum_{i\le n}d_k(i)=\frac{n(\ln n)^{k-1}}{(k-1)!}+\frac{k\gamma-1}{(k-2)!}n(\ln n)^{k-2}+O_k(n(\ln n)^{k-3}). 此时次项和主项的比值约为 \frac{(k-1)(k\gamma-1)}{\ln n}，因此对于稍大的 k，需要 \ln n 比 k^2 大很多以后最高次项才会比较准确。

再回到 1.1。这里 r=2^k，并且 G_k(s)=\prod_p(1-p^{-s})^{2^k}\sum_{a\ge0}(a+1)^kp^{-as}. 为了计算次项还需要 G_k'(1)。令 H_k(z)=\sum\limits_{a\ge0}(a+1)^kz^a，对 G_k(s) 取对数求导可以得到 \frac{G_k'(1)}{G_k(1)}=\sum_p\ln p\left(\frac{2^k}{p-1}-\frac{\sum\limits_{a\ge0}a(a+1)^kp^{-a}}{\sum\limits_{a\ge0}(a+1)^kp^{-a}}\right). 由于提出 \zeta(s)^{2^k} 时已经消掉了一次项，上式中每个素数对应的项为 O(\frac{\ln p}{p^2})，因此绝对收敛。于是 \sum d(i)^k 的前两项系数分别为 A_k=\frac{G_k(1)}{(2^k-1)!},\qquad B_k=\frac{G_k(1)}{(2^k-2)!}\left(2^k\gamma-1+\frac{G_k'(1)}{G_k(1)}\right), 即 \sum_{i\le n}d(i)^k=A_kn(\ln n)^{2^k-1}+B_kn(\ln n)^{2^k-2}+O_k(n(\ln n)^{2^k-3}).

对于 k=2，有 G_2(s)=\frac1{\zeta(2s)}，所以 \frac{G_2'(1)}{G_2(1)}=-2\frac{\zeta'(2)}{\zeta(2)}，进而有 A_2=\frac1{\pi^2}\approx0.101,\qquad B_2=\frac3{\pi^2}\left(4\gamma-1-2\frac{\zeta'(2)}{\zeta(2)}\right)\approx0.744. 因此 \sum_{i\le n}d(i)^2=0.101n(\ln n)^3+0.744n(\ln n)^2+O(n\ln n). 对于 n = 10^4 \sim 10^5 的常用区间，常数相当于翻一倍，不过还是只有 \dfrac{1}{5} 。

对于 k=3，有 \sum\limits_{a\ge0}(a+1)^3z^a=\frac{1+4z+z^2}{(1-z)^4}，因此 G_3(s)=\prod_p(1-p^{-s})^4(1+4p^{-s}+p^{-2s}). 数值计算有 G_3(1)\approx0.05，因此 A_3=\frac{G_3(1)}{7!}\approx 10^{-5}. 同时 \frac{G_3'(1)}{G_3(1)}\approx6.63，所以 B_3=\frac{G_3(1)}{6!}\left(8\gamma-1+\frac{G_3'(1)}{G_3(1)}\right)\approx7.0\times10^{-4}, 此时 \frac{B_3}{A_3}\approx72。因此，尽管 \sum d(i)^3 渐进意义下是 7\log，但是实际上 \ln^6 的部分是远大于 \ln ^7 的。实际上，对于 10^3 \sim 10^4 的 n ，\ln^4 的部分最大。真的会有人写这个吗？？？

1.4 统一分析

考虑积性函数 f，设对于任意素数 p 都有 f(p)=c，其中 c 为正常数整数，并且对 \operatorname{Re}s>\frac12 有 \sum_{a\ge 0}f(p^a)p^{-as}=1+cp^{-s}+O(p^{-2\operatorname{Re}s}), 其中 O 中的常数与 p 无关。令 F(s)=\sum_{n\ge1}\frac{f(n)}{n^s}=\prod_p\sum_{a\ge0}f(p^a)p^{-as}. 我们可以提出 \zeta(s)^c，写成 F(s)=\zeta(s)^cG(s),\qquad G(s)=\prod_p(1-p^{-s})^c\sum_{a\ge0}f(p^a)p^{-as}. 由于 (1-z)^c(1+cz+O(z^2))=1+O(z^2)，G(s) 中每个素数对应的 Euler 因子均为 1+O(p^{-2\operatorname{Re}s})，因此 G(s) 在 \operatorname{Re}s>\frac12 绝对收敛。

设 G(s)=\sum\limits_{n\ge1}\frac{g(n)}{n^s}，由 F(s)=\zeta(s)^cG(s) 有 f=d_c*g, 其中 d_c(n) 为有序分解 n=n_1n_2\dots n_c 的方案数。于是 \sum_{i\le n}f(i)=\sum_{b\le n}g(b)\sum_{a\le n/b}d_c(a). 对于固定的 c\ge2，广义 Dirichlet 除数问题给出 \sum_{a\le x}d_c(a)=xP_{c-1}(\ln x)+O_{c,\epsilon}\left(x^{1-\frac1c+\epsilon}\right), 其中 P_{c-1} 为 c-1 次多项式。由于 G(s) 在 \operatorname{Re}s>\frac12 绝对收敛，可以取 1-\frac1c+\epsilon>\frac12，从而 \sum_{b\ge1}\frac{|g(b)|}{b^{1-\frac1c+\epsilon}}<\infty. 将上式代入即可得到 \sum_{i\le n}f(i)=nQ_{c-1}(\ln n)+O_{c,\epsilon}\left(n^{1-\frac1c+\epsilon}\right), 其中 Q_{c-1} 仍为 c-1 次多项式。特别地，由 1.3 中的展开可以得到前两项 \sum_{i\le n}f(i)=\frac{G(1)}{(c-1)!}n(\ln n)^{c-1}+\frac{G'(1)+(c\gamma-1)G(1)}{(c-2)!}n(\ln n)^{c-2}+O(n(\ln n)^{c-3}).

因此在上述条件成立时，f(p)=c 决定了 \log 的次数，有 \sum_{i\le n}f(i)=\Theta(n\log^{c-1}n), 其中还需要 G(1)\neq0。可以证明，对于非整数的 c 也有类似结论。

例如考虑 f(n)=q^{\omega(n)}，其中 \omega(n) 为不同素因子的个数，q 为正常数整数。对于 a\ge1 有 f(p^a)=q，因此一个 Euler 因子为 1+qz+qz^2+\dots=1+\frac{qz}{1-z}=\frac{1+(q-1)z}{1-z}. 所以 F(s)=\zeta(s)^qG_q(s), G_q(s)=\prod_p(1-p^{-s})^{q-1}(1+(q-1)p^{-s}). 后一个 Euler 因子的展开为 1+O(p^{-2\operatorname{Re}s})，因此满足上面的条件，从而 \sum_{i\le n}q^{\omega(i)}\sim C_qn(\ln n)^{q-1}, 其中 C_q=\frac1{(q-1)!}\prod_p\left(1-\frac1p\right)^{q-1}\left(1+\frac{q-1}{p}\right).

特别地，q=2 时 G_2(s)=\prod_p(1-p^{-2s})=\frac1{\zeta(2s)}, 因此 \sum_{i\le n}2^{\omega(i)}\sim\frac6{\pi^2}n\ln n. 而 2^{\omega(i)} 正好是 i 的 square free factor 个数，所以如果对于每个 i\le n 枚举所有 square free factor，总操作次数为 \Theta(n\log n)。

1.1 和 1.2 也可以看成这一结论的特例。对于 d_k(n) 有 d_k(p)=k 且 Dirichlet 级数恰好为 \zeta(s)^k，所以 G(s)=1；对于 d(n)^k 有 d(p)^k=2^k，并且素数幂处满足 \sum_{a\ge0}(a+1)^kp^{-as}=1+2^kp^{-s}+O(p^{-2\operatorname{Re}s}), 所以对应 c=2^k，得到 n\log^{2^k-1}n。

需要注意的是，\omega(n) 本身并不属于上面的情形，因为它不是积性函数。但是可以直接交换求和，\sum_{i\le n}\omega(i)=\sum_{p\le n}\left\lfloor\frac np\right\rfloor=n\sum_{p\le n}\frac1p+O(\pi(n)). 可以证明，\sum\limits_{p\le n}\frac1p=\ln\ln n+M+o(1)，以及 \pi(n)=O(\frac n{\ln n})，得到 \sum_{i\le n}\omega(i)=n\ln\ln n+Mn+o(n). 因此对于每个 i 枚举其所有不同素因子的总代价是 \Theta(n\log\log n)。

1.5 Misc

ChatGPT 大哥对我进行了指导，包括展开 7 次多项式，部分复变内容，搜索一些不知道名字的定理，和少量 Laurent 级数。原来【】的用户名并不是这个，好吧。

实际上常数就是很小，但是 \ln^7 还是过于超前了。