根号 $n$ 提出来怎么变 $n$ 了啊
by 日居月诸 @ 2020-12-04 15:01:58
@[日居月诸](/user/73032) 啊（
原来是这里出问题了
谢谢大佬
by AffineRing @ 2020-12-04 15:04:25
- 结合数论分块，单次求和的代价为$\sqrt{n}$
- 递归求解$F(x)$时，$x$可能的取值总共有$\sqrt{n}$个，即不同的$\lfloor n/x\rfloor$的个数
- 每个值只会求解到一次，所以对于每个$x$，转移的代价都是$\sqrt{x}$。
所以总复杂度
$$
\sum_{i=1}^{\sqrt{n}}\left(i+\sqrt{n/i}\right)
$$
很显然后面的比前面大。因此只考虑后面。
$$
\sum_{i=1}^{\sqrt{n}}\sqrt{n/i}=\int_{0}^{\sqrt{n}}\sqrt{\frac{n}{x}}
$$
并且
$$
\int \sqrt{\frac{n}{x}}=\sqrt n\int x^{-\frac{1}{2}}=2n\sqrt{x}
$$
然后根据牛顿-莱布尼茨公式
$$
\int_{0}^{\sqrt{n}}\sqrt{\frac{n}{x}}=2\sqrt n\sqrt{\sqrt{n}}=2n^{\frac{3}{4}}
$$
这应该就没问题了。
by AffineRing @ 2020-12-04 15:05:26
其实问题挺多，但不严格的话问题不大（？）
比如积分漏积分变量，式子直接用等号链接而不加 $O$。。。
by 日居月诸 @ 2020-12-04 15:07:21