整除分块简介

取整函数引理

不等式转化：

\[ \lfloor x \rfloor \ge k \Longleftrightarrow x \ge k\\ \lfloor x \rfloor < k \Longleftrightarrow x < k\\ \lceil x \rceil > k \Longleftrightarrow x > k\\ \lceil x \rceil \le k \Longleftrightarrow x \le k\\ \]

整除分块

求：

\[ \sum_{i=1}^{m}{\lfloor \frac{n}{i}\rfloor} \]

我们发现，\(\lfloor \frac{n}{i} \rfloor\) 最多只有 \(2\sqrt{n}\) 个值。我们考虑将相同的值一次计算出来。最重要的问题就是知道区间的起点和终点，即

\[ \begin{align*} l&=\min_{\lfloor \frac{n}{i}\rfloor = k}{\{i\}}\\ r&=\max_{\lfloor \frac{n}{i}\rfloor = k}{\{i\}} \end{align*} \]

我们用 \(l_i\) 和 \(r_i\) 表示第 \(i\) 段区间的左右边界。容易发现，对于 \(i>1\)，\(l_i=r_{i-1}+1\)。又因为 \(l_1=1\)，我们只要知道前一个区间的右边界，就能知道当前的左边界了。

假设我们已知 \(l_i\)，要求出 \(r_i\)。

设 \(k=\lfloor \frac{n}{l_i} \rfloor\)，\(r_i\) 为使 \(\lfloor \frac{n}{r_i} \rfloor \ge k\) 的最大值。 我们注意到 \(\lfloor \frac{n}{r_i} \rfloor \ge k\) 等价于

\[ \frac{n}{r_i} \ge k \]

从而

\[ r_i\le \frac{n}{k} \]

因为 \(r_i\) 是整数，因此 \(r_i = \lfloor \frac{n}{k}\rfloor\)，即

\[ r_i=\left\lfloor{\frac{n}{\lfloor \frac{n}{l_i} \rfloor}}\right\rfloor \]

写一个 for 循环，循环求出 \(l_i\) 对应的 \(r_i\)，更新答案，并使 \(l_{i+1}=r_i+1\) 。

时间复杂度 \(O(\sqrt{n})\)