企业官网建设流程全解析

OI-wiki 数论分块（整除分块）完全指南：原理、性质、扩展与代码实战

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

数论分块（又称整除分块）是 OI / ICPC 中处理形如 $\sum_{i=1}^n f(i),g!\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ 这类和式的经典技巧：由于 $\lfloor n/i\rfloor$ 的取值在 $1\sim n$ 上只分成 $O(\sqrt n)$ 段，整段整段地累加即可把朴素 $O(n)$ 的求和优化到 $O(\sqrt n)$。本文以 OI-wiki 的 数论分块文档 为骨架，结合仓库内 代码实现 与 测试样例，系统讲解其思想、严格数学性质、算法过程、向上取整 / 多维 / 任意指数三类扩展，并通过 UVa11526 H(n) 与 Codeforces 1954E 两道例题给出可直接运行的完整解法。

数论分块常用于配合莫比乌斯反演等技巧，也是杜教筛等递归筛法复杂度分析的基础，是数论、组合计数题目中高频使用的基础工具。

思路：从"双曲线下整点"说起

假设要统计 $y=11/x$ 双曲线在第一象限、$x\in[1,11]$ 范围内下方（含边界）的整点个数，这等价于计算和式

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

这是前文一般形式在 $f(k)=1,\ g(k)=k$ 时的特例。朴素做法是逐列求和：第 $i$ 列有 $\lfloor 11/i\rfloor$ 个整点，需要做 $n$ 次除法与累加。

但观察上图可以发现：这些列的整点高度 $\lfloor 11/i\rfloor$ 并不是逐列变化的，而是分成若干段连续的、高度相同的列，每一段构成一个矩形点阵。例如 $i=4,5$ 两列高度相同，$i=6,7$ 两列高度相同。因此只要知道每段（块）的宽度，就能用矩形面积（宽度 × 高度）快速累加，把 $n$ 次单点运算压缩成 $O(\sqrt n)$ 次块级运算——这就是整除分块（数论分块）的基本思路。

数学性质：$\lfloor n/i\rfloor$ 的取值集合 $D(n)$

要严谨地使用数论分块，需要先弄清 $\lfloor n/i\rfloor$ 到底有多少种不同取值、以及每种取值对应的 $i$ 落在哪个区间。定义取值集合

$$ D(n)=\left{\left\lfloor\frac{n}{i}\right\rfloor : 1\le i\le n,\ i\in\mathbb N_+\right}. $$

OI-wiki 文档给出了 $D(n)$ 的四个核心性质。

性质 1：不同取值只有 $O(\sqrt n)$ 个

$|D(n)|\le 2\sqrt n$。证明按 $i$ 与 $\sqrt n$ 的关系分类：

• 当 $i\le\sqrt n$ 时，$i$ 至多取 $\sqrt n$ 个值，故 $\lfloor n/i\rfloor$ 至多 $\sqrt n$ 个不同取值；
• 当 $i>\sqrt n$ 时，$\lfloor n/i\rfloor\le n/i<\sqrt n$，同样至多 $\sqrt n$ 个不同取值。

两边合计即得 $|D(n)|\le 2\sqrt n$。这正是数论分块复杂度 $O(\sqrt n)$ 的根源。

性质 2：$D(n)$ 的精确刻画

设 $s=\lfloor\sqrt n\rfloor$，则 $D(n)$ 中的元素从小到大依次为

$$ 1<2<\cdots<s-1<s\le\left\lfloor\frac{n}{s}\right\rfloor<\left\lfloor\frac{n}{s-1}\right\rfloor<\cdots<\left\lfloor\frac{n}{2}\right\rfloor<\left\lfloor\frac{n}{1}\right\rfloor=n, $$

进而有精确大小 $|D(n)|=\lfloor\sqrt{4n+1}\rfloor-1$。

证明的关键是：对 $1\le i\le s$，有 $\lfloor n/\lfloor n/i\rfloor\rfloor=i$，即 $i\mapsto\lfloor n/i\rfloor$ 在 ${i:1\le i\le s}$ 上是一一映射。两段取值唯一可能重叠的元素是 $s$ 与 $\lfloor n/s\rfloor$，据此分析 $s=\lfloor n/s\rfloor$ 何时成立（等价于 $s^2\le n<s^2+s$），最终得到 $|D(n)|=\lfloor\sqrt{4n+1}\rfloor-1$。这一精确结果比粗糙的 $2\sqrt n$ 界更贴近实际块数，可用于精确估算常数。

性质 3：单块的左右端点

对于 $d\in D(n)$，所有满足 $\lfloor n/i\rfloor=d$ 的整数 $i$ 恰好构成连续区间

$$ \left\lfloor\frac{n}{d+1}\right\rfloor+1\le i\le\left\lfloor\frac{n}{d}\right\rfloor . $$

证明即解不等式 $d\le n/i<d+1$ 得 $n/(d+1)<i\le n/d$，再利用 $i\in\mathbb N_+$ 取整。该性质还揭示了图像对称性：每个块的右端点集合恰为 $D(n)$——因为整幅双曲线图像关于直线 $y=x$ 对称，图的左半部分（按 $i$ 分块）与右半部分（按 $\lfloor n/i\rfloor$ 分块）一一对应。

性质 4：递归封闭性

对 $m\in D(n)$，有 $D(m)\subseteq D(n)$。因为设 $m=\lfloor n/k\rfloor$，则对任意 $i\in\mathbb N_+$，

$$ \left\lfloor\frac{m}{i}\right\rfloor=\left\lfloor\frac{\lfloor n/k\rfloor}{i}\right\rfloor=\left\lfloor\frac{n}{ki}\right\rfloor\in D(n), $$

第二个等号用到取整函数关于嵌套分式的性质。这意味着：如果需要递归地应用数论分块（函数在 $n$ 处的值依赖它在 $m\in D(n)\setminus{n}$ 处的值），那么整个计算过程涉及的取值集合与右端点集合始终都在 $D(n)$ 内部，不会"扩大"。典型的应用是杜教筛，其时空复杂度分析正是建立在这条性质之上（见文档末尾引用的"杜教筛的时空复杂度分析"一文）。

过程：标准数论分块伪代码

有了上述性质，算法的过程就非常直接。要计算

$$ \sum_{i=1}^n f(i),g!\left(\left\lfloor\frac{n}{i}\right\rfloor\right), $$

将标号 $i=1,2,\cdots,n$ 按照 $\lfloor n/i\rfloor$ 的取值分块。由于取值相同的标号是一段连续整数 $[l,r]$，该块的贡献为

$$ \left(\sum_{i=l}^{r} f(i)\right)\cdot g!\left(\left\lfloor\frac{n}{l}\right\rfloor\right). $$

左侧的 $\sum_{i=l}^r f(i)$ 通常用 $f$ 的前缀和 $s(k)=\sum_{i=1}^k f(i)$ 表达：$s(r)-s(l-1)$。若 $s(\cdot)$ 能在 $O(1)$ 内求出（解析式已知或已预处理前缀和），则总复杂度为 $O(\sqrt n)$。

块与块的衔接规则是：当前块左端点 $l$ 等于上一块右端点加 $1$；当前块右端点 $r=\left\lfloor\dfrac{n}{\lfloor n/l\rfloor}\right\rfloor$（由性质 3 立即得到）。OI-wiki 文档给出的伪代码如下：

$$ \begin{array}{l} \textbf{Algorithm }\text{Sum}(f,g,n):\ \textbf{Input. }n,\ s(k)=\sum_{i=1}^k f(k),\ g(k).\ \textbf{Output. }S(n)=\sum_{i=1}^n f(i),g(\lfloor n/i\rfloor).\ \textbf{Method.}\ \begin{array}{ll} 1 & l\gets 1\ 2 & \textit{result}\gets 0\ 3 & \textbf{while } l\le n \textbf{ do}\ 4 & \qquad r\gets \left\lfloor\dfrac{n}{\lfloor n/l\rfloor}\right\rfloor\ 5 & \qquad \textit{result}\gets \textit{result}+(s(r)-s(l-1))\cdot g!\left(\left\lfloor\dfrac{n}{l}\right\rfloor\right)\ 6 & \qquad l\gets r+1\ 7 & \textbf{end while}\ 8 & \textbf{return }\textit{result} \end{array} \end{array} $$

实现时注意两点：一是循环终止条件 $l\le n$ 必须用整数除法与long long防止溢出；二是 $g(\lfloor n/l\rfloor)$ 在整个块内是常数，务必提到块外只算一次。

扩展一：向上取整的数论分块

当和式中出现向上取整时，利用恒等式

$$ \left\lceil\frac{n}{i}\right\rceil=\left\lfloor\frac{n-1}{i}\right\rfloor+1 $$

可化归为向下取整：

$$ \sum_{i=1}^n f(i),g!\left(\left\lceil\frac{n}{i}\right\rceil\right) =f(n),g(1)+\sum_{i=1}^{n-1}f(i),g!\left(\left\lfloor\frac{n-1}{i}\right\rfloor+1\right). $$

注意两点变化：求和上限由 $n$ 变为 $n-1$；$i=n$ 这一项被单独拆出（因为 $\lfloor(n-1)/n\rfloor=0$）。这一转化在下一节 Codeforces 1954E 的实现中还会以 $\lceil a/k\rceil=(a-1)/k+1$ 的形式出现。

扩展二：多维数论分块

对于同时含多个取整式的和式

$$ \sum_{i=1}^{n}f(i),g!\left(\left\lfloor\frac{n_1}{i}\right\rfloor,\left\lfloor\frac{n_2}{i}\right\rfloor,\cdots,\left\lfloor\frac{n_m}{i}\right\rfloor\right), $$

需要保证每一块内所有取整式的取值都不变，因此多维的块是各一维块的交集。给定左端点 $l$ 后，右端点取所有一维右端点中的最小值：

$$ r=\min\left{\left\lfloor\frac{n_1}{\lfloor n_1/l\rfloor}\right\rfloor,\left\lfloor\frac{n_2}{\lfloor n_2/l\rfloor}\right\rfloor,\cdots,\left\lfloor\frac{n_m}{\lfloor n_m/l\rfloor}\right\rfloor\right}. $$

如上图所示，二维情形下每个一维分块的断点互相交错，取二者的交叠区间即可同时保证两个取整式不变。二维形式最为常见，只需把一维伪代码中的右端点计算替换为

$$ r\gets\min\left{\left\lfloor\frac{n_1}{\lfloor n_1/l\rfloor}\right\rfloor,\left\lfloor\frac{n_2}{\lfloor n_2/l\rfloor}\right\rfloor\right}. $$

扩展三：任意指数数论分块

更一般地，可以计算

$$ \sum_{i=1}^{\lfloor n^{\alpha/\beta}\rfloor} f(i),g!\left(\left\lfloor\frac{n^\alpha}{i^\beta}\right\rfloor\right), $$

其中 $\alpha,\beta$ 为正实数，基本形式即 $\alpha=\beta=1$。定义

$$ D(n,\alpha,\beta)=\left{\left\lfloor\frac{n^\alpha}{i^\beta}\right\rfloor: i=1,2,\cdots,\lfloor n^{\alpha/\beta}\rfloor\right}, $$

OI-wiki 文档证明了两条性质：

1. $|D(n,\alpha,\beta)|\le 2n^{\alpha/(1+\beta)}$（按 $i$ 与 $n^{\alpha/(1+\beta)}$ 的大小关系分类讨论）；
2. 对 $d\in D(n,\alpha,\beta)$，满足 $\lfloor n^\alpha/i^\beta\rfloor=d$ 的 $i$ 取值范围为

$$ \left\lfloor\frac{n^{\alpha/\beta}}{(d+1)^{1/\beta}}\right\rfloor+1\le i\le\left\lfloor\frac{n^{\alpha/\beta}}{d^{1/\beta}}\right\rfloor . $$

据此可在 $O(n^{\alpha/(1+\beta)})$ 时间内完成任意指数的数论分块。例子：当 $\alpha=\beta=1/2$ 时，和式

$$ \sum_{i=1}^n f(i),g!\left(\left\lfloor\sqrt{\frac{n}{i}}\right\rfloor\right) $$

可在 $O(n^{1/3})$ 内解决，且已知左端点 $l$ 时右端点为 $r=\left\lfloor n/\lfloor\sqrt{n/l}\rfloor^2\right\rfloor$。这类"半次方"分块在部分数论题目中能进一步压复杂度，是扩展性最强的形态。

例题实战：两个可直接运行的实现

OI-wiki 文档为两道例题提供了仓库内的完整代码与输入输出样例，下面结合源码讲解。

例 1：UVa11526 H(n)——一维数论分块模板

题目要求 $T$ 组数据，每组给定 $n$，输出 $\sum_{i=1}^n\lfloor n/i\rfloor$，即基本形式中 $f\equiv 1$、$g(k)=k$。朴素求和是 $O(n)$，用数论分块则为 $O(T\sqrt n)$。

仓库内 sqrt-decomposition_1.cpp 是完整实现：

#include <iostream> long long H(int n) { long long res = 0; // 储存结果 int l = 1, r; // 块左端点与右端点 while (l <= n) { r = n / (n / l); // 计算当前块的右端点 // 累加这一块的贡献到结果中。乘上 1LL 防止溢出 res += 1LL * (r - l + 1) * (n / l); l = r + 1; // 左端点移到下一块 } return res; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t, n; std::cin >> t; while (t--) { std::cin >> n; std::cout << H(n) << '\n'; } return 0; }

代码与伪代码逐行对应：第 7 行r = n / (n / l)即右端点公式 $\lfloor n/\lfloor n/l\rfloor\rfloor$；第 9 行块贡献 $=$ 块宽度 $(r-l+1)\times$ 块高度 $n/l$，1LL强制 64 位累加防止int溢出；第 10 行跳到下一块。仓库给出的样例输入 sqrt-decomposition_1.in（两组数据 $n=5,10$）对应期望输出 sqrt-decomposition_1.ans 为10与27（验证：$5/1+\cdots+5/5=5+2+1+1+1=10$；$10$ 的对应和为 $10+5+3+2+2+1+1+1+1+1=27$）。

例 2：Codeforces 1954E Chain Reaction——二维数论分块 + 差分

题目给出一排 $n$ 只怪兽，血量 $a_i$；一次攻击使一段连续存活的怪兽血量减 $k$，血量不大于 $0$ 即死亡。要求对所有 $k$ 求出击杀全部怪兽所需攻击次数，其中 $n,a_i\le 10^5$。

解答思路（文档）：令 $a_0=0$。击杀前 $i-1$ 只怪兽需要 $T(k,i-1)$ 次攻击，击杀第 $i-1$ 只需要的 $\lceil a_{i-1}/k\rceil$ 次攻击都能顺带延伸打到第 $i$ 只，因此击杀第 $i$ 只只需再补

$$ \max\left{0,\left\lceil\frac{a_i}{k}\right\rceil-\left\lceil\frac{a_{i-1}}{k}\right\rceil\right} $$

次攻击，于是总攻击次数

$$ T(k,n)=\sum_{i=1}^n\max\left(0,\left\lceil\frac{a_i}{k}\right\rceil-\left\lceil\frac{a_{i-1}}{k}\right\rceil\right). $$

对每个 $k$ 分别求和不可行，改为：对每个 $i$，把数列 ${T(k,i)}k$ 看成对 ${T(k,i-1)}k$ 逐项加 $\max(0,\lceil a_i/k\rceil-\lceil a{i-1}/k\rceil)$ 得到的。利用二维数论分块，这次"逐项加"可以拆成 $O(\sqrt{a{i-1}}+\sqrt{a_i})$ 段区间加，且每段加的是常数；最后只做一次求前缀和即可得到全部答案。总复杂度 $O(\sum\sqrt{a_i})$。

仓库内 sqrt-decomposition_2.cpp 是完整实现，核心循环如下：

for (int i = 0; i < n; ++i) for (int l = 1, r;; l = r + 1) { r = std::min(l < a[i] ? (a[i] - 1) / ((a[i] - 1) / l) : N, l < a[i + 1] ? (a[i + 1] - 1) / ((a[i + 1] - 1) / l) : N); // 二维数论分块 if (r == N) break; int x = (a[i + 1] - 1) / l - std::max(a[i] - 1, 0) / l; if (x > 0) ans[l] += x, ans[r + 1] -= x; // 累加贡献 } ++ans[0]; // ⌈a/l⌉=(a-1)/l+1 的式子当 a=0 时不成立，需要修正

实现细节值得注意：

• 利用 $\lceil a/k\rceil=(a-1)/k+1$ 把向上取整统一成向下取整，所以(a[i]-1)/((a[i]-1)/l)就是针对 $\lceil a_i/l\rceil$ 的一维块右端点（取整式(a[i]-1)/l不变）；
• 右端点对两个维度取std::min，正是"多维数论分块 = 一维分块交集"思想的落地；
• 由于 $\lceil a_i/k\rceil-\lceil a_{i-1}/k\rceil$ 在同一块内为常数 $x$，用差分数组ans[l] += x; ans[r+1] -= x实现区间加，最后一遍前缀和还原答案；
• ++ans[0]修正 $a=0$ 时 $\lceil a/l\rceil=(a-1)/l+1$ 不成立的特殊情况（$a_0=0$）。

仓库样例输入 sqrt-decomposition_2.in 为 $n=3,\ a=[5,2,7]$，对应输出 sqrt-decomposition_2.ans 为10 6 4 3 2 2 1，即 $k=1,2,3,4,5,6,7$ 时的答案（最大血量 $7$ 以上 $k$ 只需 1 次，故输出共 $7$ 项）。该题对"所有 $k$ 批量求解 + 数论分块 + 差分"的组合是区间批量贡献类题目的经典范式。

习题巩固

OI-wiki 文档给出如下习题，建议按顺序练习：

• UVa11526 H(n)：一维数论分块模板题，即例 1；
• Luogu P2261「CQOI2007」余数求和：将 $\sum_{i=1}^n k\bmod i$ 改写为 $nk-\sum_{i=1}^n i\lfloor k/i\rfloor$，用数论分块处理后者，综合考察分块与等差/前缀和技巧；
• Luogu P3455「POI2007」ZAP-Queries：与莫比乌斯反演结合的标准应用，验证"数论分块常与莫比乌斯反演结合"这一文档论断。

参考资料与注释

• OI-wiki 数论分块：docs/math/number-theory/sqrt-decomposition.md，本文章节结构、性质证明与伪代码均以此为准；
• 例 1 实现：docs/math/code/sqrt-decomposition/sqrt-decomposition_1.cpp；
• 例 2 实现：docs/math/code/sqrt-decomposition/sqrt-decomposition_2.cpp；
• 示例输入输出：例 1 见 sqrt-decomposition_1.in 与 sqrt-decomposition_1.ans；例 2 见 sqrt-decomposition_2.in 与 sqrt-decomposition_2.ans；
• 图解资源：一维示意图 与 多维示意图，另有可复现插图的 脚本；
• 性质 4（递归封闭性）是杜教筛复杂度分析的基础，详见杜教筛一章；文档同时引用了"杜教筛的时空复杂度分析"一文作为延伸阅读。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki