整除分块某引理证明。

· · 个人记录

将 1\sim n 中所有 \lfloor \frac{n}{i}\rfloor 的结果合并为一个长度为 m 的升序序列 a，则 \lfloor\frac{n}{a_j}\rfloor=a_{m-j+1}。

注意到原命题等价为：

考虑如何证明 $\lfloor\frac{n}{a_j}\rfloor$ 严格单调递减，注意到它单调不增是显然的，然后命题可以等价于 $\lfloor\frac{n}{a_j}\rfloor$ 取值有 $m$ 种，等价于 $\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$ 取值有 $m$ 种。这个取值种类数就是整除分块的右端点数，和整除分块的块内值的种类数显然相同。