关于整除分块的一个小证明

求证 $lfloor dfrac{n}{i} floor$ 只有 $sqrt{n}$ 种取值。

当 $i in [1,sqrt{n}]$ 时,取值范围在 $[sqrt{n},n]$,最多有 $sqrt{n}$ 种取值。

当 $iin [sqrt{n},n]$ 时,取值范围在 $[1,sqrt{n}]$,显然最多有 $sqrt{n}$ 种。

综上,成立。

原文地址:https://www.cnblogs.com/xugangfan/p/15175086.html