数论 Part：整数分块及其应用

· · 个人记录

\text{定义}

整数分块是用于快速计算下取整的求和式的一种算法，可以将形如以下形式的求和从 O(n) 的时间复杂度优化至 O(\sqrt{n})。

\sum_{i=1}^n f(i)\left\lfloor\frac{n}{i}\right\rfloor.

\text{一些例子}

\text{例 1}

例 1：给定正整数 n，求出以下和式的值。

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

这是整数分块最基本的形式。

引理 1：给定正整数 n，对于任意的正整数 i\leq n，\left\lfloor\frac{n}{i}\right\rfloor 至多只有 2\sqrt{n} 种取值。

证明：当 1\leq i\leq\sqrt{n} 时，显然至多有 \sqrt{n} 种取值。当 \sqrt{n}<i\leq n 时，显然有 \left\lfloor\frac{n}{i}\right\rfloor\leq \sqrt{n}，故也至多有 \sqrt{n} 种取值。综上至多有 2\sqrt{n} 种取值。

另一件显而易见的事情是： \left\lfloor\frac{n}{i}\right\rfloor 相同的 i 一定是连续的，故称之为一 块。此处不予证明。

引理 2：给定正整数 n，若一个块的左端点是 l，则其右端点为 \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor。

证明：为了便于书写，记 k=\left\lfloor\frac{n}{l}\right\rfloor，则有 k\leq\frac{n}{l}。显然任意在块中的 i 都有 \left\lfloor\frac{n}{i}\right\rfloor=k，则有任意在块中的 i 都有 \left\lfloor\frac{n}{k}\right\rfloor\geq\left\lfloor\frac{n}{\frac{n}{i}}\right\rfloor=i，即 i 的上界为 \left\lfloor\frac{n}{k}\right\rfloor。

所以对于这一个和式，可以使用一个左端点指针，求出对应块的右端点然后 O(1) 求和，再将左端点赋值为右端点加一，重复以上操作直到左端点超过 n 结束。即如下代码。

cin >> n;
for (int l = 1, r; l <= n; l = r + 1) {
  r = n / (n / i);
  Sum += (n / i) * (r - l + 1);
}

因为我们是依照 \left\lfloor\frac{n}{i}\right\rfloor 枚举的，由引理 1 可得其取值至多 2\sqrt{n} 个，所以时间复杂度为 O(\sqrt{n})。

\text{例 2}

给定正整数 n，求出以下和式：

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

与前一例相比，求和的东西多了一个与 i 有关的系数。

我们一样对后面的向下取整进行整数分块后，若当前块左端点为 l，右端点为 r，令 k=\left\lfloor\frac{n}{l}\right\rfloor 则这一段的和为 \sum_{i=l}^r ki=k\sum_{i=1}^r i，显然可以套用公式或者前缀和预处理求出贡献。即如下代码：

for (int l = 1, r; l <= n; l = r + 1) {
  r = n / (n / i);
  Sum += (l + r) * (r - l + 1) / 2 * (k / i);
}

或

for (int i = 1; i <= n; i ++) Pre[i] = Pre[i - 1] + i;
for (int l = 1, r; l <= n; l = r + 1) {
  r = n / (n / i);
  Sum += (Pre[r] - Pre[l - 1]) * (k / i);
}

更一般地，对于后面这一种写法，可发现将算法的时间复杂度的瓶颈由求和式转化为了求前缀和，也就是说，关键在于能否 O(1) 而不是 O(n) 的求出前缀和，即将原来的和式转化成了另一个和式的求解，并且去掉了一个下取整符号，时间复杂度乘以了 O(\sqrt{n})。

\text{习题}

\text{P2261 [CQOI2007] 余数求和}

根据取模的性质，可以得到 k\bmod i=k - i \times\left\lfloor\frac{k}{i}\right\rfloor。故有如下变换：

\begin{aligned} G(n,k)&= \sum_{i=1}^n k\bmod i\\ &=\sum_{i=1}^n (k-i\times\left\lfloor\frac{k}{i}\right\rfloor)\\ &=nk -\sum_{i=1}^ni\left\lfloor\frac{k}{i}\right\rfloor. \end{aligned}

显然与例 2 形式基本一致，尽管 n 不一定等于 k，但本质是相同的，只需要修改 l,r 的上界。

\text{P3935 Calculating}

根据一些数论基础知识可发现，f(i) 表示 i 的约数个数，则有：

f(n)=\sum_{i=1}^n[i\ |\ n].

题目所求和式可以拆分为两个自 1 开始的前缀和作差，则令：

g(n)=\sum_{i=1}^n f(i).

故有：

\begin{aligned} g(n)&=\sum_{i=1}^n f(i)\\ &= \sum_{i=1}^n \sum_{j=1}^i [j\ |\ i]\\ &= \sum_{i=1}^n \sum_{j=1}^n [j\ |\ i]\\ &= \sum_{j=1}^n \sum_{i=1}^n [j\ |\ i]\\ &= \sum_{j=1}^n\left\lfloor\frac{n}{i}\right\rfloor. \end{aligned}

与例 1 形式完全相同，最后输出 g(r)-g(l-1) 即可。

\text{P2424 约数和}

与上题类似，有：

f(n)=\sum_{i=1}^n i[i\ |\ n]

同样地，使用前缀和作差，定义 g(n)=\sum_{i=1}^n f(i)，故有：

\begin{aligned} g(n)&=\sum_{i=1}^n f(i)\\ &= \sum_{i=1}^n\sum_{j=1}^i j[j\ |\ i]\\ &= \sum_{i=1}^n\sum_{j=1}^n j[j\ |\ i]\\ &= \sum_{j=1}^n\sum_{i=1}^n j[j\ |\ i]\\ &= \sum_{j=1}^nj\sum_{i=1}^n [j\ |\ i]\\ &= \sum_{j=1}^nj\left\lfloor\frac{n}{j}\right\rfloor.\\ \end{aligned}

与例 2 形式相同，输出答案为 g(r)-g(l-1) 即可。