感谢这篇文章的作者
整除分块主要解决求解 $\sum\limits_{i=1}^n \lfloor \frac{n}{i} \rfloor$ 的值。
一看这个公式，可能毫无头绪，但画张图你就有点思路了：（$n=11$）
（灰色线：$y=\frac{11}{x}$，绿色点：$y=\lfloor \frac{11}{x} \rfloor$，橙色线：仅为辅助）
这张图其实就是在提示我们：
- $\lfloor \frac{n}{i} \rfloor$ 的值随着 $i$ 的增长而非单调递减
- $\lfloor \frac{n}{i} \rfloor$ 的值往往会在一段区间内相等
所以，我们就有一个思路了，就是求出所有值（下面的“值”都代指的是 $\lfloor \frac{n}{i} \rfloor$）相等的极大区间集，然后就可以快速统计了。
有人问，这不就是个常数级别的优化吗，怎么能叫“快速”呢？其实区间个数总是 $O(\sqrt{n})$ 级别，最多约 $2 \times \sqrt{n}$。
证明：
我们把 $i$ 分成两部分去考虑，一部分是 $i \leq \sqrt{n}$，另一部分是 $i>\sqrt{n}$。
在第一部分内，$i$ 也就只有 $\sqrt{n}$ 种取值，$\lfloor \frac{n}{i} \rfloor$ 最多只有约 $\sqrt{n}$ 种取值。
在第二部分内，$\lfloor \frac{n}{i} \rfloor$ 在 $i$ 最小时（$i=\sqrt{n}+1$）会达到最大值，约 $\sqrt{n}$；而上面说“$\lfloor \frac{n}{i} \rfloor$ 的值随着 $i$ 的增长而非单调递减”，所以易得 $\lfloor \frac{n}{i} \rfloor$ 最多也只有约 $\sqrt{n}$ 种取值。
$\lfloor \frac{n}{i} \rfloor$ 的总取值种数最多只有第一、二部分的取值个数和，即 $2 \times \sqrt{n}$，证毕。
然后，我们就考虑求区间集了，以下设 $l$ 为这个区间的左端点，$r$ 为这个区间的右端点，且 $l$ 已知。
设 $v=\lfloor \frac{n}{l} \rfloor$，其实 $r$ 就是最大的 $i$ 满足 $v=\lfloor \frac{n}{i} \rfloor$，显然（条件）等价于 $i=\lfloor \frac{n}{v} \rfloor$，带入 $v$ 后即可求出 $r=\left\lfloor \dfrac{n}{\lfloor \frac{n}{l} \rfloor} \right\rfloor$。
于是乎，最上面那个问题就可以求解了，答案就是 $\sum (r-l+1) \times v$。