注意根式向下取整

根据 $^{[1]}$，在 $x\ge1$ 且 $\alpha>0,\alpha\ne 1$ 时有 $$ \sum\limits_{n\le x}\sigma_\alpha(n)=\dfrac{\zeta(\alpha+1)}{\alpha+1}x^{\alpha+1}+O(x^{\max\{1,\alpha\}}), $$ 所以 $\sigma_{1/2}(n)$ 应该是 $O(\sqrt n)$ 的。更精细的上界就不知道了（ $^{[1]}$: Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001, p. 60.

设： $$n=\prod_{i}p_i^{e_i}$$ $$f(n)=\sum_{d|n}d^{1/2}=\prod_{i}\frac{p_i^{(e_i+1)/2}-1}{p_i^{1/2}-1}$$ 设 $n$ 为前 $k$ 个质数之积，则： $$f(n)=\prod_{i=1}^k(p_i^{1/2}+1)$$ - 设 $g(n)=f(n)/\sqrt n$ - 下面是 $k$ 与 $g(n)$ 的关系： - $k=10,g(n)=19.652466$。 - $k=38,g(n)=377.979437$。 - $k=58,g(n)=1409.553112$。 - 因此可以基本判定 $g(n)=\omega(\sqrt n)$。 虽然但是，这个复杂度很可能是作者对 $n$ 的每个因数求积性函数导致的，在这种情况下，有显然的 $O(\text{因子分解})$ 的方法。 - 如果是这个问题，我建议作者不应该关注这个问题，而应该提升自己的算法能力。

设： $$n=\prod_{i}p_i^{e_i}$$ $$f(n)=\sum_{d|n}d^{1/2}=\prod_{i}\frac{p_i^{(e_i+1)/2}-1}{p_i^{1/2}-1}$$ 设 $n$ 为前 $k$ 个质数之积，则： $$f(n)=\prod_{i=1}^k(p_i^{1/2}+1)$$ - 设 $g(n)=f(n)/\sqrt n$ - 下面是 $k$ 与 $g(n)$ 的关系： - $k=4,g(n)=5.369817$。 - $k=25,g(n)=125.336655$。 - $k=168,g(n)=127804.033107$。 - $k=1229,g(n)=1610696887547.172911$。 - $k=9592,g(n)=840539887651625723218616123392$。 - 因此可以基本判定 $f(n)=\omega(\sqrt n)$，且 $g(n)\sim O(1)^{\sqrt{k}}$。 虽然但是，这个复杂度很可能是作者对 $n$ 的每个因数求积性函数导致的，在这种情况下，有显然的 $O(\text{因子分解})$ 的方法。 - 如果是这个问题，我建议作者不应该关注这个问题，而应该提升自己的算法能力。

考虑到楼主的评论，在这里说明一下：“根式是否向下取整”根本不会影响该函数的渐近复杂度。

而且以上即对最坏复杂度做出分析，因为平均复杂度已经有人分析了（

我的错（尴尬