$O(n\log^2 n)$
by liqingyang @ 2024-04-02 17:10:05
@[Winston12321_](/user/396994) $\Theta(n \log^2n)$。
by NaCly_Fish @ 2024-04-02 17:12:10
使用结论调和数 $H_n \sim \ln n+\gamma$，最后用积分估计即可。
by NaCly_Fish @ 2024-04-02 17:13:24
orz
by jijidawang @ 2024-04-02 17:14:40
@[liqingyang](/user/272088) 感谢
by Winston12321_ @ 2024-04-02 17:42:48
@[NaCly_Fish](/user/115864) 感谢
by Winston12321_ @ 2024-04-02 17:43:01
$$\sum_{i=1}^n \sum_{j=1}^{\lfloor n/i\rfloor }\lfloor n/ij\rfloor\sim \sum_{i=1}^n H_{\lfloor n/i \rfloor}\sim \sum_{i=1}^n (n/i)\ln{\lfloor n/i \rfloor}\sim n\sum_{i=1}^n\frac{\ln n-\ln i}{i}\sim n\ln^2 n - n\sum_{i=1}^{n}\frac{\ln i}{i}$$
注意到
$$\sum_{i=1}^{n}\frac{\ln i}{i}\sim \int_{1}^n \frac{\ln x}{x}dx=\int_{1}^n \ln(x)d(\ln x)=\frac{\ln^2 n}{2}$$
所以原式大约是 $\displaystyle\frac{1}{2}n\ln^2 n$
by 蒟蒻君HJT @ 2024-04-02 18:00:56
@[蒟蒻君HJT](/user/131591) 感谢
by Winston12321_ @ 2024-04-02 19:41:35