整除分块

一. 核心定理

整除分块，又称数论分块，其核心是一个定理。

定理：设 $\operatorname{diff}$ 函数为求不同数值的个数，如 $\operatorname{diff}\{1,1,3,4,6,6,6\}=4$，则 $\mathop{\operatorname{diff}}\limits_{i=1}^{i\le n}\left\lfloor\dfrac{n}{i}\right\rfloor$ 最大不超过 $2\sqrt{n}$。

证明：

1. 考虑 $i\in[1,\sqrt{n}]$，最多 $\sqrt{n}$ 个。所以 $\mathop{\operatorname{diff}}\limits_{i=1}^{i\le\sqrt{n}}\left\lfloor\dfrac{n}{i}\right\rfloor$ 最大不超过 $\sqrt{n}$。

2. 考虑 $i\in(\sqrt{n},n]$，$\left\lfloor\dfrac{n}{i}\right\rfloor$ 的值单调不增。$\left\lfloor\dfrac{n}{\left\lceil\sqrt{n}\right\rceil}\right\rfloor$ 的值最大为 $\sqrt{n}$，$\left\lfloor\dfrac{n}{n}\right\rfloor$ 为 $1$。所以 $\mathop{\operatorname{diff}}\limits_{i=\left\lceil\sqrt{n}\right\rceil}^{i\le n}\left\lfloor\dfrac{n}{i}\right\rfloor$ 最大不超过 $\sqrt{n}$。

证毕。

二. 确定分界点

上一个标题中，我们认识到整除分块复杂度的正确性。这一个标题将会讲解如何确定块与块之间的分界点。

设 $g_n(x)$ 为大于等于 $x$ 且被 $n$ 整除的值与 $x$ 被 $n$ 整除的值相同的最大整数。可用公式表示为：

$$\left\lfloor\dfrac{n}{x}\right\rfloor=\left\lfloor\dfrac{n}{g_n(x)}\right\rfloor,\left\lfloor\dfrac{n}{x}\right\rfloor>\left\lfloor\dfrac{n}{g_n(x)+1}\right\rfloor$$

定理：$g_n(x)=\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor$

证明：只要证明了上面“可用公式表示为”的两个式子成立，即可完成证明。

1. 证明第一个式子

   首先引入三个显然的东西：

   • $\left\lfloor n\right\rfloor\le n$。

   • 如果 $n\le m$，那么 $\left\lfloor n\right\rfloor\le \left\lfloor m\right\rfloor$。

   • 如果 $n\in \mathbb{Z}$，那么 $\left\lfloor n\right\rfloor=n$。

   开始证明：

   1. 证明 $x\le\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor$

      $$\begin{gather} \dfrac{n}{x}\ge\left\lfloor\dfrac{n}{x}\right\rfloor\\ \text{又}\because\dfrac{n}{x},\left\lfloor\dfrac{n}{x}\right\rfloor\ne0\\ \Longrightarrow\dfrac{n}{\frac{n}{x}}\le\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\\ \Longrightarrow\left\lfloor\dfrac{n}{\frac{n}{x}}\right\rfloor\le\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor\\ \Longrightarrow\left\lfloor x\right\rfloor\le\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor\\ \Longrightarrow x\le\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor\\ \end{gather}$$

      这条结论在接下来的证明中一直会用到。

      这一步相当于是证明了 $x\le g_n(x)$。

   2. 证明 $\left\lfloor\dfrac{n}{x}\right\rfloor\ge\left\lfloor\dfrac{n}{g_n(x)}\right\rfloor$

      $$\begin{gather} x\le g_n(x)\\ \text{又}\because x,g_n(x)\ne0\\ \Longrightarrow\dfrac{n}{x}\ge\dfrac{n}{g_n(x)}\\ \Longrightarrow\left\lfloor\dfrac{n}{x}\right\rfloor\ge\left\lfloor\dfrac{n}{g_n(x)}\right\rfloor\\ \end{gather}$$

   3. 证明 $\left\lfloor\dfrac{n}{x}\right\rfloor\le\left\lfloor\dfrac{n}{g_n(x)}\right\rfloor$

      $$\begin{gather} \text{即证}\left\lfloor\dfrac{n}{x}\right\rfloor\le\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{\left\lfloor \frac{n}{x}\right\rfloor}\right\rfloor}\right\rfloor\\ \text{设}x'=\left\lfloor\dfrac{n}{x}\right\rfloor\\ \text{即证}x'\le\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{\left\lfloor x'\right\rfloor}\right\rfloor}\right\rfloor,\text{该式已被证明}\\ \end{gather}$$

   综上所述，$\left\lfloor\dfrac{n}{x}\right\rfloor=\left\lfloor\dfrac{n}{g_n(x)}\right\rfloor$

2. 证明第二个式子

   我们先设一下带余除法，带余除法是数论证明的常用手段，它能有效地消掉下去整号。

   设 $n=kx+b~(0\le b<x)$，则 $\left\lfloor\dfrac{n}{x}\right\rfloor=k$。

   设 $n=pk+q~(0\le q<k)$，则 $\left\lfloor\dfrac{n}{k}\right\rfloor=p$。

   $$\begin{gather} \text{若证}\left\lfloor\dfrac{n}{x}\right\rfloor>\left\lfloor\dfrac{n}{g_n(x)+1}\right\rfloor\\ \text{即证}\left\lfloor\dfrac{n}{x}\right\rfloor>\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{\left\lfloor \frac{n}{x}\right\rfloor}\right\rfloor+1}\right\rfloor\\ \text{即证}k>\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{k}\right\rfloor+1}\right\rfloor\\ \text{即证}k>\left\lfloor\dfrac{n}{p+1}\right\rfloor\\ \end{gather}$$

   这里需要先证一个小结论：若 $a,b,c\in\mathbb{Z},a>\left\lfloor\dfrac{b}{c}\right\rfloor$，则 $ac>b$。

   $$\begin{gather} \because a\in\mathbb{Z},a>\left\lfloor\dfrac{b}{c}\right\rfloor\\ \therefore a>\dfrac{b}{c}\\ \therefore ac>b\\ \end{gather}$$

   接着主线的证明：

   $$\begin{gather} \text{即证}k(p+1)>n\\ \text{即证}n<pk+k\\ \text{又}\because n=pk+q,q<k.\text{该式成立} \end{gather}$$

综上所述，$g_n(x)=\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{x}\right\rfloor}\right\rfloor$。

三. 应用

主要用于解决求类似 $\sum\limits_{i=1}^{i\le n}\left\lfloor\dfrac{n}{i}\right\rfloor$ 的式子，如果直接暴力求时间复杂度是 $O(n)$ 的，使用整除分块可以降到 $O(\sqrt{n})$。

求 $\sum\limits_{i=1}^{i\le n}\left\lfloor\dfrac{n}{i}\right\rfloor$ 的代码示例：

for (int il = 1, ir = min(n, n / (n / il)); ; il = ir + 1, ir = min(n, n / (n / il))) {
    // ...
    if (ir == n) break;
}

注意 l > n 后运行这个语句会出现除零错，所以要在每个循环体的末尾判 break 而非 for 的第二个位置。

例题：

[CQOI2007]余数求和

[POI2007]ZAP-Queries