所以 $\sqrt{n}$ 做法不就假了么？
by Xy_top @ 2023-04-02 20:15:52
内层可以预处理
by 霖ux @ 2023-04-02 20:16:08
@[霖ux](/user/520914) 哦，我傻逼了，谢谢提醒。
by Xy_top @ 2023-04-02 20:17:14
补充一下，两层整除分块的复杂度是 $O(n^{3/4})$
by XeCtera @ 2023-04-02 20:18:06
@[icyM3tra](/user/38785) 我要是预处理 $1$~$i$ 的 $\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor$ 暴力整除分块是 $n\sqrt n$ 的，有没有更优的方法呢？
by Xy_top @ 2023-04-02 20:20:18
@[Xy_top](/user/637796) 注意到 $\sum\limits_{i=1}^n\lfloor\frac ni\rfloor=\sum\limits_{i=1}^n\sigma_0(i)$，线性筛之后求前缀和即可
by XeCtera @ 2023-04-02 20:21:35
$\sigma_0(n)=\sum\limits_{d|n}1$ 表示因子个数。
by XeCtera @ 2023-04-02 20:22:10
@[icyM3tra](/user/38785) 这个我知道，但是能否证明一下为什么 $\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor=\sum\limits_{i=1}^n d(i)$
by Xy_top @ 2023-04-02 20:25:16
@[icyM3tra](/user/38785) 哦没事儿了会了，谢谢大佬
by Xy_top @ 2023-04-02 20:27:10
$\sum\limits_{i=1}^n \lfloor \frac{n}{i}\rfloor$ 就相当于问 $[1,n]$ 之间有多少个 $i$ 的倍数，反过来考虑不就是问因数和。
by HMZHMZHMZ @ 2023-04-02 20:27:45