整除分块

Posted on 2018-09-01 Views:

一维情况

在莫比乌斯反演中，我们经常需要计算类似如下的和式：

$\sum_{i = 1}^n \left\lfloor \frac{n}{i} \right\rfloor$

如果朴素计算的话时间复杂度是

的，这个代价对于很多多询问的题目来说是在是太高了，因此我们需要更快的方法。

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

证明：我们首先证明：对于所有的 $k \le \lfloor \sqrt n \rfloor$ 我们都可以找到一个使得 $\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$

因此，通过适当地选择

我们已经可以让 $\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$ ，我们证明对于这些， $\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$ 个， $\lfloor n / i \rfloor \ge \lfloor \sqrt n\rfloor$ 此时也有 $\lfloor \sqrt n\rfloor$ 种取值。

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

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

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

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

推论：所在的一段结束于 $\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)$ 种取值

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

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

证明：类似一维情况。