一维情况

在莫比乌斯反演中，我们经常需要计算类似如下的和式： \[ \sum_{i = 1}^n \left\lfloor \frac{n}{i} \right\rfloor \] 如果朴素计算的话时间复杂度是 \(O(n)\) 的，这个代价对于很多多询问的题目来说是在是太高了，因此我们需要更快的方法。

结论：\(\left\lfloor \frac{n}{i} \right\rfloor\) 总共只有 \(O(\sqrt n)\) 种不同的取值。

证明：我们首先证明：对于所有的 \(k \le \lfloor \sqrt n \rfloor\) 我们都可以找到一个 \(i\) 使得 \(\lfloor n / i \rfloor = k\)：

令 \(i = \left\lfloor n / k\right\rfloor \ge k\)： \[ ik \le n < (i + 1)k = ik + k \le ik + i = i(k + 1) \\ \Rightarrow k \le n / i < k + 1 \\ \Rightarrow \left\lfloor n / i \right\rfloor = k \] 因此，通过适当地选择 \(i\) 我们已经可以让 \(\lfloor n / i \rfloor\) 取到 \(\lfloor \sqrt n\rfloor\) 个值，因为这些 \(i \ge \lfloor \sqrt n\rfloor\)，因此我们进一步推得：对于所有 \(i \ge \lfloor \sqrt n\rfloor\)，\(\lfloor n / i \rfloor \le \lfloor \sqrt n\rfloor\) 共有 \(\lfloor \sqrt n\rfloor\) 种取值。

对于所有的 \(i \le \lfloor \sqrt n \rfloor\)，我们证明对于这些 \(i\)，\(\lfloor n / i \rfloor\) 的值各不相同，因为假设存在一对相邻的 \(i - 1, i\)，使得 \(\lfloor {n \over i - 1} \rfloor = \lfloor {n \over i} \rfloor = k\)，则： \[ k \le {n \over i - 1} < k + 1 \\ k \le {n \over i} < k + 1 \\ \Rightarrow {n \over i - 1} - {n \over i} = {n \over i(i - 1)} < 1 \] 而事实上因为 \(i \le \lfloor \sqrt n\rfloor\)，\(i(i - 1) < n \Rightarrow {n \over i(i - 1)} > 1\)，矛盾。

因此对于 \(i \le \lfloor \sqrt n\rfloor\) 的 \(\lfloor \sqrt n\rfloor\) 个 \(i\)，\(\lfloor n / i \rfloor \ge \lfloor \sqrt n\rfloor\) 此时也有 \(\lfloor \sqrt n\rfloor\) 种取值。

因此总共大约有 \(2\lfloor \sqrt n \rfloor\) 种取值，证毕。

这样子我们就可以一段一段地计算了，时间复杂度骤降为 \(O(\sqrt n)\)，但是一段到底到哪里结束呢？

结论：值为 \(k\) 的一段结束于 \(i = \lfloor n / k\rfloor\)。

证明：随着 \(i\) 的变大，\(n / i - \lfloor n / i\rfloor\) 的值必定单调递减，临界点就是 \(n / i = \lfloor n / i\rfloor = k\)，此时 \(i = n / k\)。考虑到此时 \(i\) 可能不是整数，因此结束位置为 \(\lfloor n / k\rfloor\)。

推论：\(i\) 所在的一段结束于 \(\lfloor n / \lfloor n / i \rfloor \rfloor\)。

有这两条结论，我们就可以很快地计算一开头和式的值了：

for (int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}

二维情况

假设 \(n < m\)，我们有时候还会碰到类似如下的和式： \[ \sum_{i = 1}^n \left\lfloor \frac{n}{i} \right\rfloor \left\lfloor \frac{m}{i} \right\rfloor \] 结论：\(\left\lfloor \frac{n}{i} \right\rfloor \left\lfloor \frac{m}{i} \right\rfloor\) 共有 \(O(\sqrt n + \sqrt m)\) 种取值

证明：我们可以这样想象：假设有一根数轴表示 \(i\) 的不同取值，\(\left\lfloor \frac{n}{i} \right\rfloor\) 用 \(O(\sqrt n)\) 个分割点把数轴分成了 \(O(\sqrt n)\) 段（姑且叫它们 \(N\) 段），\(\left\lfloor \frac{m}{i} \right\rfloor\) 用 \(O(\sqrt m)\) 个分割点在不同的位置把数轴也分成了 \(O(\sqrt m)\) 段（姑且叫它们 \(M\) 段），现在把这些段 overlay 一下，你会发现现在总共有 \(O(\sqrt n + \sqrt m)\) 个分割点把数轴分成了 \(O(\sqrt n + \sqrt m)\) 段，每一段的取值可能不同（想一下，两个点只有不完全在相同的 \(N\) 段和 \(M\) 段时计算出来的 \(\left\lfloor \frac{n}{i} \right\rfloor \left\lfloor \frac{m}{i} \right\rfloor\) 才可能不一样！）

结论：\(i\) 所在的一段结束于 \(\min\{\lfloor n / \lfloor n / i \rfloor \rfloor, \lfloor m / \lfloor m / i \rfloor \rfloor\}\)。

证明：类似一维情况。