OI-wiki 数论分块整除分块完全指南原理、性质、扩展与代码实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki数论分块又称整除分块是 OI / ICPC 中处理形如 $\sum_{i1}^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 两道例题给出可直接运行的完整解法。数论分块常用于配合莫比乌斯反演等技巧也是杜教筛等递归筛法复杂度分析的基础是数论、组合计数题目中高频使用的基础工具。思路从双曲线下整点说起假设要统计 $y11/x$ 双曲线在第一象限、$x\in[1,11]$ 范围内下方含边界的整点个数这等价于计算和式$$ \sum_{i1}^{11}\left\lfloor\frac{11}{i}\right\rfloor . $$这是前文一般形式在 $f(k)1,\ g(k)k$ 时的特例。朴素做法是逐列求和第 $i$ 列有 $\lfloor 11/i\rfloor$ 个整点需要做 $n$ 次除法与累加。但观察上图可以发现这些列的整点高度 $\lfloor 11/i\rfloor$ 并不是逐列变化的而是分成若干段连续的、高度相同的列每一段构成一个矩形点阵。例如 $i4,5$ 两列高度相同$i6,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)$ 中的元素从小到大依次为$$ 12\cdotss-1s\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\rfloorn, $$进而有精确大小 $|D(n)|\lfloor\sqrt{4n1}\rfloor-1$。证明的关键是对 $1\le i\le s$有 $\lfloor n/\lfloor n/i\rfloor\rfloori$即 $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 ns^2s$最终得到 $|D(n)|\lfloor\sqrt{4n1}\rfloor-1$。这一精确结果比粗糙的 $2\sqrt n$ 界更贴近实际块数可用于精确估算常数。性质 3单块的左右端点对于 $d\in D(n)$所有满足 $\lfloor n/i\rfloord$ 的整数 $i$ 恰好构成连续区间$$ \left\lfloor\frac{n}{d1}\right\rfloor1\le i\le\left\lfloor\frac{n}{d}\right\rfloor . $$证明即解不等式 $d\le n/id1$ 得 $n/(d1)i\le n/d$再利用 $i\in\mathbb N_$ 取整。该性质还揭示了图像对称性每个块的右端点集合恰为 $D(n)$——因为整幅双曲线图像关于直线 $yx$ 对称图的左半部分按 $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_{i1}^n f(i),g!\left(\left\lfloor\frac{n}{i}\right\rfloor\right), $$将标号 $i1,2,\cdots,n$ 按照 $\lfloor n/i\rfloor$ 的取值分块。由于取值相同的标号是一段连续整数 $[l,r]$该块的贡献为$$ \left(\sum_{il}^{r} f(i)\right)\cdot g!\left(\left\lfloor\frac{n}{l}\right\rfloor\right). $$左侧的 $\sum_{il}^r f(i)$ 通常用 $f$ 的前缀和 $s(k)\sum_{i1}^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_{i1}^k f(k),\ g(k).\ \textbf{Output. }S(n)\sum_{i1}^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 r1\ 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\rfloor1 $$可化归为向下取整$$ \sum_{i1}^n f(i),g!\left(\left\lceil\frac{n}{i}\right\rceil\right) f(n),g(1)\sum_{i1}^{n-1}f(i),g!\left(\left\lfloor\frac{n-1}{i}\right\rfloor1\right). $$注意两点变化求和上限由 $n$ 变为 $n-1$$in$ 这一项被单独拆出因为 $\lfloor(n-1)/n\rfloor0$。这一转化在下一节 Codeforces 1954E 的实现中还会以 $\lceil a/k\rceil(a-1)/k1$ 的形式出现。扩展二多维数论分块对于同时含多个取整式的和式$$ \sum_{i1}^{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_{i1}^{\lfloor n^{\alpha/\beta}\rfloor} f(i),g!\left(\left\lfloor\frac{n^\alpha}{i^\beta}\right\rfloor\right), $$其中 $\alpha,\beta$ 为正实数基本形式即 $\alpha\beta1$。定义$$ D(n,\alpha,\beta)\left{\left\lfloor\frac{n^\alpha}{i^\beta}\right\rfloor: i1,2,\cdots,\lfloor n^{\alpha/\beta}\rfloor\right}, $$OI-wiki 文档证明了两条性质$|D(n,\alpha,\beta)|\le 2n^{\alpha/(1\beta)}$按 $i$ 与 $n^{\alpha/(1\beta)}$ 的大小关系分类讨论对 $d\in D(n,\alpha,\beta)$满足 $\lfloor n^\alpha/i^\beta\rfloord$ 的 $i$ 取值范围为$$ \left\lfloor\frac{n^{\alpha/\beta}}{(d1)^{1/\beta}}\right\rfloor1\le i\le\left\lfloor\frac{n^{\alpha/\beta}}{d^{1/\beta}}\right\rfloor . $$据此可在 $O(n^{\alpha/(1\beta)})$ 时间内完成任意指数的数论分块。例子当 $\alpha\beta1/2$ 时和式$$ \sum_{i1}^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 文档为两道例题提供了仓库内的完整代码与输入输出样例下面结合源码讲解。例 1UVa11526 H(n)——一维数论分块模板题目要求 $T$ 组数据每组给定 $n$输出 $\sum_{i1}^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-l1)\times$ 块高度 $n/l$1LL强制 64 位累加防止int溢出第 10 行跳到下一块。仓库给出的样例输入 sqrt-decomposition_1.in两组数据 $n5,10$对应期望输出 sqrt-decomposition_1.ans 为10与27验证$5/1\cdots5/55211110$$10$ 的对应和为 $1053221111127$。例 2Codeforces 1954E Chain Reaction——二维数论分块 差分题目给出一排 $n$ 只怪兽血量 $a_i$一次攻击使一段连续存活的怪兽血量减 $k$血量不大于 $0$ 即死亡。要求对所有 $k$ 求出击杀全部怪兽所需攻击次数其中 $n,a_i\le 10^5$。解答思路文档令 $a_00$。击杀前 $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_{i1}^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)/l1 的式子当 a0 时不成立需要修正实现细节值得注意利用 $\lceil a/k\rceil(a-1)/k1$ 把向上取整统一成向下取整所以(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[r1] - x实现区间加最后一遍前缀和还原答案ans[0]修正 $a0$ 时 $\lceil a/l\rceil(a-1)/l1$ 不成立的特殊情况$a_00$。仓库样例输入 sqrt-decomposition_2.in 为 $n3,\ a[5,2,7]$对应输出 sqrt-decomposition_2.ans 为10 6 4 3 2 2 1即 $k1,2,3,4,5,6,7$ 时的答案最大血量 $7$ 以上 $k$ 只需 1 次故输出共 $7$ 项。该题对所有 $k$ 批量求解 数论分块 差分的组合是区间批量贡献类题目的经典范式。习题巩固OI-wiki 文档给出如下习题建议按顺序练习UVa11526 H(n)一维数论分块模板题即例 1Luogu P2261「CQOI2007」余数求和将 $\sum_{i1}^n k\bmod i$ 改写为 $nk-\sum_{i1}^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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考