引入

整除分块是数论问题中非常常用的技巧，先来看一个简单的问题：

已知，给定一个 $n$，求 $ f(n) = \sum_{i=1}^n \left \lfloor \frac{n}{i} \right \rfloor $ 的值。

先假设 $1 \le n \le 10^6 $，第一反应肯定是 $O(n)$ 遍历一遍 $1 \sim n$ 直接求和，轻松得到答案。

int ans = 0;
for(int i=1; i<=n; i++){
    ans += n/i;
}

但如果 $1 \le n \le 10^{9} $ ，甚至 $10^{12}$ 呢，显然就不能 $O(n)$ 暴力了，这就得用到接下来要介绍的整除分块的内容。

找规律找规律

我们先试着计算一下 $\left \lfloor \frac{n}{i} \right \rfloor$ 前几项（几十项）的值，比如 $n = 16$：

| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16
| ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | | $\left \lfloor \frac{n}{i} \right \rfloor$ |16 | 8 | 5 | 4 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1

可以发现 $\left \lfloor \frac{n}{i} \right \rfloor$ 的取值在连续的一段区间内是相同的，那么就启发我们是否可以将其分为若干块分别进行计算呢，这就是整除分块的核心思想了。

分块数量（时间复杂度分析）

根据数学知识可以知道 $\left \lfloor \frac{n}{i} \right \rfloor$ 的值的集合大小最多为 $2\sqrt{n}$，我们可以简单证明一下这个数学现象：

对于正整数 $i$，当 $i \le \sqrt{n}$ 时，由于 $i$ 最多有 $\sqrt{n}$ 种取值，$\left \lfloor \frac{n}{i} \right \rfloor$ 最多也只能有 $\sqrt{n}$ 种取值；

当 $i \gt \sqrt{n}$ 时，由于 $i \gt n$ 之后，$\left \lfloor \frac{n}{i} \right \rfloor$ 的值始终为 $0$，而在 $\sqrt{n} \lt i \le n$ 时 $i$ 最多也只有 $\sqrt{n}$ 种取值，$\left \lfloor \frac{n}{i} \right \rfloor$ 最多也只能有 $\sqrt{n}$ 种取值。

综上所述，$\left \lfloor \frac{n}{i} \right \rfloor$ 的值的集合大小最多为 $2\sqrt{n}$ ，这样整除分块的时间复杂度就为 $O(\sqrt{n})$。

分块边界

先让 $l$ 为分块的左边界，那么这块的单个值 $k = \left \lfloor \frac{n}{l} \right \rfloor$ ，这样右边界 $r$ 就是值为 $k$ 的最大下标 $i$，也就是说要找满足 $i \le \frac{n}{k}$ 的最大的 $i$，即 $r = max(i) = \frac{n}{k}$ ，将 $k$ 代入，得到 $r = \left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor $ 。

这样每块的左右边界都可以用一个确定的式子计算得到，这样分块的值就为单值 × 区间长度，即 $k * (r-l+1)$。

模板

ll division_block(ll n){
    ll res = 0;
    for(ll l = 1, r; l <= n; l = r + 1){
        r = n / (n / l);
        res += n / l * (r - l + 1);
    }
    return res;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com