第 18 章 数论与组合计数基础 · 知识细节练习

考点：整除的概念（A1）。

解析：$b \mid a$ ⇔ 存在整数 $k$ 使 $a = kb$ ⇔ a % b == 0。✅ 正确

排除法：无（判断题）。混淆点：整除是"模为 0"的特殊情形——% 是检验整除的工具。

关联 · 模运算的定义（D3）：余数为 0 即整除。

考点：素数的定义（A2）。

解析：素数 = 大于 1、只有 1 和自身两个正因数。✅ 正确

排除法：无（判断题）。混淆点：1 不是素数（A3）；2 是最小且唯一的偶素数。

关联 · 合数与 1（A3）：分类边界。

考点：合数与 1（A3）。

解析：1 只有 1 个正因数，既不是素数也不是合数。✅ 正确

排除法：无（判断题）。混淆点：0 也不是素数/合数，但一般不纳入"大于 1 的自然数"讨论。

关联 · 素数的定义（A2）：三分类：素/合/1。

考点：约数与倍数（A4）。

解析：12 的正约数：1, 2, 3, 4, 6, 12，共 6 个。正确答案 A。

排除法：B（5）漏算 1 或 12；C 是数本身；D 无依据。

关联 · 约数个数（I3）：逐 i 试除统计。

考点：质因数分解与唯一分解定理（A5）。

解析：任何大于 1 的整数可唯一分解为质因子乘积（不计顺序）——$60 = 2^2 \times 3 \times 5$。✅ 正确

排除法：无（判断题）。混淆点："不计顺序"即唯一；计顺序则有重排多种写法。

关联 · 质因数分解输出（I5）：代码版。

考点：奇偶性（A6）。

解析：奇 + 奇 = 偶（$(2k+1)+(2m+1) = 2(k+m+1)$）。正确答案 A。

排除法：B 错；C/D 与和是否素/合无关（如 3+5=8 合数、1+2 不算两个奇数）。

关联 · 整除的概念（A1）：奇偶即模 2 的余数。

考点：最大公约数的定义（B1）。

解析：$\gcd(24, 36) = 12$（$24 = 2^3 \times 3$，$36 = 2^2 \times 3^2$，取公共低次幂）。正确答案 A。

排除法：B（6）漏了因子 2；C（4）漏了 3；D（72）是 lcm。

关联 · 辗转相除法（B2）：求 gcd 的标准算法。

考点：辗转相除法（B2）。

解析：$\gcd(a,b) = \gcd(b, a\%b)$，$b=0$ 返回 $a$；余数严格递减，必终止。✅ 正确

排除法：无（判断题）。混淆点：终止条件是 $b = 0$ 而非 $a = 0$。

关联 · 辗转相除迭代版（J1）：代码版输出 12。

考点：gcd 与质因数分解（B3）。

解析：gcd = 公共质因子的最低次幂乘积——分解后"取小"。✅ 正确

排除法：无（判断题）。混淆点：lcm 是"取大"（B4）——一对镜像。

关联 · 最小公倍数（B4）：取大 vs 取小。

考点：最小公倍数（B4）。

解析：$\mathrm{lcm}(4,6) = 12$（$4 = 2^2$，$6 = 2 \times 3$，取最高次幂）。正确答案 A。

排除法：B（24）是乘积；C（6）是 gcd；D 无依据。

关联 · 最小公倍数输出（J3）：公式 $a \times b / \gcd$。

考点：互质（B5）。

解析：$\gcd = 1$ 即互质；两个不同质数显然互质（无公共质因子）。✅ 正确

排除法：无（判断题）。混淆点：合数也可能互质（如 8 与 9）。

关联 · gcd 与质因数分解（B3）：无公共质因子 ⇔ 互质。

考点：真题计算 gcd（B6）。

解析：$252 = 2^2 \times 3^2 \times 7$、$105 = 3 \times 5 \times 7$ → 公共部分 $3 \times 7 = 21$。正确答案 A。

排除法：B（3）漏 7；C（7）漏 3；D（15）是 105 的因子但不是公共的（252 无 5）。

关联 · 辗转相除法（B2）：$252 \% 105 = 42$，$105 \% 42 = 21$，$42 \% 21 = 0$。

考点：更相减损的原理（B7）。

解析：$\gcd(a, b) = \gcd(b, a-b)$——同时减去 $b$ 不改变公约数；反复减相当于取模。✅ 正确

排除法：无（判断题）。混淆点：减法版大数时慢（多次减），取模版快——本质相同。

关联 · 更相减损版（J4）：代码版输出 12。

考点：试除法判定素数（C1）。

解析：试除 $2 \sim n-1$；优化后只需到 $\sqrt{n}$（若 $n$ 有因子 $d$，必有因子 $\leq \sqrt{n}$）。✅ 正确

排除法：无（判断题）。混淆点：试到 $\sqrt{n}$ 是"充分且必要"的界限。

关联 · 试除范围到平方根（C2）：界限的量化。

考点：试除范围到平方根（C2）。

解析：$\sqrt{97} \approx 9.8$，试除 $i \times i \leq 97$ 即 $i \leq 9$。正确答案 A。

排除法：B/C 是未优化的范围；D 无意义。

关联 · 试除次数统计（I2）：$n=100$ 时循环 9 次。

考点：埃氏筛的思想（C3）。

解析：从 2 开始，把每个质数的倍数全部标记；未标记者即质数。✅ 正确

排除法：无（判断题）。混淆点：标记从 $p^2$ 开始（H3），合数被最小质因子标掉。

关联 · 埃氏筛输出质数（K1）：代码版。

考点：埃氏筛的复杂度（C4）。

解析：$n/2 + n/3 + n/5 + \cdots$ 调和级数 ≈ $O(n \log \log n)$。正确答案 A。

排除法：B 是线性筛的复杂度（C5）；C 是朴素；D 无依据。

关联 · 线性筛（欧拉筛）（C5）：$O(n)$ 的进一步优化。

考点：线性筛与欧拉筛（C5）。

解析：每个合数只被最小质因子筛一次 → $O(n)$。✅ 正确

排除法：无（判断题）。混淆点：i % primes[j] == 0 时 break 是"只筛一次"的关键（K3）。

关联 · 线性筛质数个数（K3）：代码版输出 8。

考点：筛法的应用（C6）。

解析：筛法 = 批量打质数表；顺带可求区间质数、约数个数（K5）。正确答案 A。

排除法：B/C/D 不是筛法的用途。

关联 · 区间质数输出（K4）：筛法 + 区间过滤。

考点：试除与筛法的选择（C7）。

解析：单个数试除 $O(\sqrt{n})$；批量筛 $O(n \log \log n)$。✅ 正确

排除法：无（判断题）。混淆点：边界——筛法内存 $O(n)$，超大 $n$ 时要权衡。

关联 · 试除法判定素数（C1）：两种场景的选择依据。

考点：向下取整（D1）。

解析：$\lfloor 7/2 \rfloor = 3$（C++ 整数除法自动向下取整）。正确答案 A。

排除法：B 是向上取整；C 是精确除法；D 无依据。

关联 · 向下取整输出（L1）：7 / 2 输出 3。

考点：向上取整（D2）。

解析：袋子数 = $\lceil n/m \rceil = (n + m - 1) / m$。正确答案 A。

排除法：B 是向下取整（会漏装）；C/D 无依据。

关联 · 向上取整输出（L2）：$10$ 件每袋 3 → 4 袋。

考点：模运算的定义（D3）。

解析：a % b 余数范围 $[0, b)$（$b > 0$、$a \geq 0$）。✅ 正确

排除法：无（判断题）。混淆点：负数被除数时 C++ 余数可为负（D4）。

关联 · 模运算输出（L3）：17 % 5 输出 2。

考点：负数取模（D4）。

解析：C++ 中余数符号与被除数一致：(-7) % 3 = -1（数学上 $-7 = 3 \times (-3) + 2$，余 2）。✅ 正确

排除法：无（判断题）。混淆点：竞赛中避免负数取模，先 (x % m + m) % m 转正。

关联 · 负数取模输出（L4）：代码输出 -1。

考点：模的加法性质（D5）。

解析：$(a+b) \% m = (a\%m + b\%m) \% m$——先拆后合结果一致。✅ 正确

排除法：无（判断题）。混淆点：用途——超大数求和防溢出。

关联 · 模的加法验证（L5）：0 0 双输出验证。

考点：模的乘法性质（D6）。

解析：$(a \times b) \% m = (a\%m) \times (b\%m) \% m$——乘法同理。✅ 正确

排除法：无（判断题）。混淆点：$a \times b$ 本身可能溢出，先取模再乘。

关联 · 模的乘法防溢出（L6）：9 的输出。

考点：模的除法不成立（D7）。

解析：除法没有类似性质：$(a/b)\%m \neq (a\%m)/(b\%m)\%m$——需逆元（提高级）。✅ 正确

排除法：无（判断题）。混淆点：P3 的代码实证输出 2 1。

关联 · 模除错误示范（P3）：两值不同的证明。

考点：加法原理（E1）。

解析：分类互斥 → 方案数相加。✅ 正确

排除法：无（判断题）。混淆点："类"不互斥会重复计数（E6）。

关联 · 分类必须互斥（E6）：适用前提。

考点：乘法原理（E2）。

解析：分步独立 → 方案数相乘。✅ 正确

排除法：无（判断题）。混淆点：每步的选择数不因前步变化时才可直乘。

关联 · 加法原理（E1）：加 vs 乘的分界。

考点：分类与分步（E3）。

解析："经 B 到 C"是两步 → 乘法：$3 \times 2 = 6$。正确答案 A。

排除法：B 把分步当分类；C/D 漏步。

关联 · 乘法原理（E2）：分步相乘。

考点：加乘混合（E4）。

解析：甲→乙是"二选一"（汽车或高铁）用加法 $2+3$，再×乙→丙的 2 → $(2+3) \times 2 = 10$。正确答案 A。

排除法：B 全加；C 把"或"当"且"相乘；D 无依据。

关联 · 分类与分步（E3）：混合题的拆解。

考点：计数与枚举验证（E5）。

解析：小规模枚举对拍、大规模用原理推广——标准验证流程。✅ 正确

排除法：无（判断题）。混淆点：对拍只能找反例不能证明，但足够实战。

关联 · DP 与枚举（第 17 章 F6）：同款验证哲学。

考点：分类必须互斥（E6）。

解析：两类有重叠时相加会重复计数——先排除重叠或改用其他方法。✅ 正确

排除法：无（判断题）。混淆点：互斥是加法原理的硬前提。

关联 · 加法原理（E1）：前提条件。

考点：排列数公式（F1）。

解析：$A(5,2) = 5 \times 4 = 20$（从 5 个里选 2 个并排顺序）。正确答案 A。

排除法：B 是 $C(5,2)$；C 是 $5^2$；D 是 $5!$。

关联 · 排列与组合的区别（F5）：有顺序用 A。

考点：全排列（F2）。

解析：$4! = 24$。正确答案 A。

排除法：B 是 $A(4,2)$；C 是 $2^4$；D 是 $2^3$。

关联 · 排列数公式（F1）：$A(n,n) = n!$。

考点：组合数公式（F3）。

解析：$C(5,2) = \dfrac{5 \times 4}{2 \times 1} = 10$。正确答案 A。

排除法：B 是 $A(5,2)$；C 是 $n$；D 无依据。

关联 · 组合数的对称性（F4）：$C(5,2) = C(5,3)$。

考点：组合数的对称性（F4）。

解析：选 $k$ 个留下 ⇔ 选 $n-k$ 个留下，一一对应。✅ 正确

排除法：无（判断题）。混淆点：对称性常用于化简计算（选小的一方）。

关联 · 组合数公式（F3）：$C(n,k) = C(n,n-k)$。

考点：排列与组合的区别（F5）。

解析：顺序有关 → A；顺序无关 → C。✅ 正确

排除法：无（判断题）。混淆点："班委分工"（有职位）是排列，"只选人"是组合。

关联 · 排列数公式（F1）：区分依据。

考点：杨辉恒等式（F6）。

解析：$C(n,k) = C(n-1,k) + C(n-1,k-1)$——最后元素"不选/选"两类。✅ 正确

排除法：无（判断题）。混淆点：这也是组合数递推计算的依据（M3/M6）。

关联 · 杨辉递推组合数（M3）：递推代码。

考点：二项和等于 2 的 n 次方（F7）。

解析：$C(3,0) + \cdots + C(3,3) = 2^3 = 8$（每个元素选/不选两种）。正确答案 A。

排除法：B 漏掉两端；C/D 无依据。

关联 · 组合数的对称性（F4）：二项和的组合意义。

考点：捆绑法（G1）。

解析：两女生捆成 1 个整体 → 4 个对象排列 $4!$，内部 $2!$ → $2! \times 4! = 48$。正确答案 A。

排除法：B 是普通全排；C 漏了整体排列；D 漏了内部。

关联 · 捆绑法计数（N3）：代码版 48。

大纲注：捆绑/插空/隔板等计数技巧在 NOI 2025 大纲中未单列，属排列组合【4】的标准应用、初赛高频。

考点：插空法（G2）。

解析：3 男先排 $3!$，产生 4 个空位，2 女插空 $A(4,2)$ → $6 \times 12 = 72$。正确答案 A。

排除法：B 是捆绑法答案；C 是普通全排；D 无依据。

关联 · 插空法计数（N4）：代码版 72。

大纲注：同 G1，属组合【4】标准应用。

考点：隔板法（G3）。

解析：7 个相同苹果排一行有 6 个空隙，插 2 块隔板分 3 组 → $C(6,2) = 15$。正确答案 A。

排除法：B（21）是 $C(7,2)$；C 是 $C(5,2)$；D 是 $C(7,3)$。

关联 · 隔板法计数（N5）：代码版 15。

大纲注：同 G1，属组合【4】标准应用。

考点：特殊元素优先（G4）。

解析：甲固定最前 → 其余 5 人任意排 $5! = 120$。正确答案 A。

排除法：B 是没固定；C/D 无依据。

关联 · 全排列（F2）：固定一个位置少一个自由度。

大纲注：同 G1，属排列【4】标准应用。

考点：有重复元素的排列（G5）。

解析：$3! / 2! = 3$（两个 A 相同，除以重复阶乘）——AAB、ABA、BAA。正确答案 A。

排除法：B 把相同 A 当不同；C/D 无依据。

关联 · 全排列（F2）：去重除以重复元素阶乘。

大纲注：多重集排列在 NOI 2025 大纲中未单列（提高级【6】才列），本处仅作排列【4】的应用保留。

考点：技巧的识别（G6）。

解析：相邻→捆绑、不相邻→插空、相同物品分组→隔板——先识别约束。✅ 正确

排除法：无（判断题）。混淆点：约束识别错则技巧用错，答案差一个量级。

关联 · 捆绑法（G1）：技巧总览。

大纲注：同 G1，属组合【4】标准应用。

考点：1 的特殊性（H1）。

解析：1 是任何数的约数，且既非素也非合。正确答案 A。

排除法：B/C 错；D——1 的约数就是 1 自己，不是"没有"。

关联 · 合数与 1（A3）：概念题代码化。

考点：组合数 k 大于 n（H2）。

解析：选不出 k 个 → 组合意义为 0（程序公式可能算错，需特判）。正确答案 A。

排除法：B/C/D 无依据。

关联 · 组合数的边界（P5）：if (k > n) return 0。

考点：筛法的起始位置（H3）。

解析：从 $p^2$ 开始：$2p, 3p, \ldots, (p-1)p$ 都有更小的质因子、已被标记。✅ 正确

排除法：无（判断题）。混淆点：从 2p 开始只是慢、不错；从 p 开始会把自己标掉（P2）。

关联 · 筛法起始位置错（P2）：错误示范输出 0。

考点：数论综合判断（H4）。

解析：三句全部正确：$\gcd \times \mathrm{lcm} = ab$（$6 \times 36 = 216 = 12 \times 18$）；不同质数互质；组合对称。✅ 正确

排除法：无（判断题）。混淆点：这是本章骨架，逐条对照各组题目。

关联 · 最小公倍数（B4）：$\gcd \times \mathrm{lcm} = ab$ 恒等式。

考点：试除判断素数（I1）。

解析：$17$ 试除 $2 \sim 4$ 均不整除 → YES。正确答案 A。

实现要点：素数判定 = 试除到 $\sqrt{n}$（i * i <= n）+ 整除即标记。手算：$17$ 不是 $2, 3, 4$ 的倍数。

排除法：B 是合数的输出；C/D 不是输出。

关联 · 试除法判定素数（C1）：概念题代码化。

考点：试除次数统计（I2）。

解析：$i = 2 \sim 10$（$10^2 = 100$），共 9 次。正确答案 A。

实现要点：i * i <= n 的循环次数 = $\lfloor \sqrt{n} \rfloor - 1$。手算：$2,3,\ldots,10$。

排除法：B 是 $n-1$；C 是 $n/2$；D 差 1。

关联 · 试除范围到平方根（C2）：范围的量化。

考点：约数个数（I3）。

解析：12 的约数 1,2,3,4,6,12 → 6 个。正确答案 A。

实现要点：约数统计 = 逐个 n % i == 0。手算：列出全部约数。

排除法：B 漏算；C 是数本身；D 无依据。

关联 · 约数与倍数（A4）：概念题代码化。

考点：输出全部约数（I4）。

解析：1 2 3 4 6 12。正确答案 A。

实现要点：约数输出 = 循环 + 整除判断 + 输出。手算：升序列出。

排除法：B 是降序；C/D 缺项或错误。

关联 · 约数个数（I3）：计数版与输出版同框架。

考点：质因数分解输出（I5）。

解析：$60 = 2 \times 2 \times 3 \times 5$ → 2 2 3 5。正确答案 A。

实现要点：分解 = 试除当前因子除尽（while）+ 剩余 n > 1 收尾。手算：$60 \to 30 \to 15 \to 5 \to 1$。

排除法：B 漏了重复的 2；C 混入合数 4；D 多出 6。

关联 · 质因数分解（唯一分解定理）（A5）：概念题代码化。

考点：质因子个数（I6）。

解析：$60 = 2^2 \times 3 \times 5$，按重数计 4 个。正确答案 A。

实现要点：分解中每除一次计数 + 收尾 +1。手算：2, 2, 3, 5。

排除法：B 按不同质因子计（2,3,5 共 3 个）；C/D 无依据。

关联 · 质因数分解输出（I5）：同框架计数版。

考点：辗转相除迭代版（J1）。

解析：$48 \% 36 = 12$，$36 \% 12 = 0$ → gcd 12。正确答案 A。

实现要点：迭代版 = while (b) { t = a % b; a = b; b = t; }。手算：取模序列 $12, 0$。

排除法：B（6）错算；C（4）无依据；D（24）是中间值。

关联 · 辗转相除法（B2）：算法代码。

考点：辗转相除过程输出（J2）。

解析：$48\%36=12$、$36\%12=0$ → 12 0。正确答案 A。

实现要点：过程输出 = 每轮打印余数。手算：逐轮写余数。

排除法：B 是输入；C 顺序反；D 漏了 0。

关联 · 辗转相除迭代版（J1）：过程与结果同源。

考点：最小公倍数输出（J3）。

解析：$\gcd(4,6)=2$，$\mathrm{lcm} = 4/2 \times 6 = 12$。正确答案 A。

实现要点：先 gcd 再 a / g * b（先除后乘防溢出）。手算：$2 \times 6 = 12$。

排除法：B 是乘积；C 是 gcd；D 无依据。

关联 · 最小公倍数（B4）：公式代码。

考点：更相减损版（J4）。

解析：$48-36=12$，$36-12=24$，$24-12=12$ → 12。正确答案 A。

实现要点：while (a != b) 大减小。手算：逐步相减。

排除法：B 是输入；C/D 无依据。

关联 · 更相减损的原理（B7）：减法版代码。

考点：多个数的 gcd（J5）。

解析：$\gcd(24,36)=12$，$\gcd(12,48)=12$，$\gcd(12,60)=12$ → 12。正确答案 A。

实现要点：逐个合并：g = gcd(g, a[i])。手算：两两相求。

排除法：B 是最大数；C 漏因子；D 无依据。

关联 · 辗转相除迭代版（J1）：两数版的推广。

考点：分数化简（J6）。

解析：$\gcd(24,36)=12$ → $24/12 : 36/12 = 2/3$。正确答案 A。

实现要点：化简 = 分子分母同除 gcd。手算：$2:3$。

排除法：B 是原分数；C 未约尽；D 错。

关联 · 最大公约数的定义（B1）：gcd 的应用。

考点：埃氏筛输出质数（K1）。

解析：20 以内质数：2, 3, 5, 7, 11, 13, 17, 19。正确答案 A。

实现要点：埃氏筛 = 质数倍数标记 + 未标记者输出。手算：逐质数划掉倍数。

排除法：B 混入 9；C 是合数；D 混入 1。

关联 · 埃氏筛的思想（C3）：算法代码。

考点：埃氏筛质数个数（K2）。

解析：20 以内质数 8 个。正确答案 A。

实现要点：筛 + 计数。手算：同上。

排除法：B（9）把 1 也算上；C 是 n；D 少一个。

关联 · 埃氏筛输出质数（K1）：计数版。

考点：线性筛质数个数（K3）。

解析：线性筛结果同为 8 个。正确答案 A。

实现要点：线性筛核心 = 每个合数用最小质因子筛一次（i % primes[j] == 0 即 break）。手算：与埃氏筛结果一致。

排除法：B（9）把 1 算上；C/D 无依据。

关联 · 线性筛（欧拉筛）（C5）：算法代码。

考点：区间质数输出（K4）。

解析：$[10, 20]$ 的质数：11, 13, 17, 19。正确答案 A。

实现要点：全量筛 + 区间过滤输出。手算：10~20 逐个判断。

排除法：B 混入 10；C 混入 15；D 混入 20。

关联 · 筛法的应用（C6）：筛 + 区间查询。

考点：筛法求约数个数（K5）。

解析：$d[10]$ 被 $i = 1, 2, 5, 10$ 各加 1 → 4。正确答案 A。

实现要点：约数筛 = 每个 i 给它的倍数 +1（反向筛法）。手算：列出 10 的约数。

排除法：B（3）漏算 1 或 10；C 是数本身；D 无依据。

关联 · 约数个数（I3）：筛法版 vs 试除版。

考点：筛法标记输出（K6）。

解析：2~10：2P 3P 4C 5P 6C 7P 8C 9C 10C → PPCPCPCCC。正确答案 A。

实现要点：标记数组输出 P/C。手算：逐数判断。

排除法：B 全 P；C 全 C；D 7 位置错。

关联 · 埃氏筛输出质数（K1）：标记视角。

考点：补全埃氏筛（K7）。

解析：从 i * i 开始标记（H3）。运行：质数个数 8。正确答案 A。

实现要点：埃氏筛三要素 = 未标记即质数 + 从 $i^2$ 标记 + 步长 $i$。手算：验证计数。

排除法：B（2i）多标但不错；C 把自己标掉（P2）；D 无依据。

关联 · 筛法的起始位置（H3）：填空版。

考点：向下取整输出（L1）。

解析：7 / 2 = 3（整数除法截断）。正确答案 A。

实现要点：C++ 整数除法 = 向下取整（正数时）。手算：$7 = 2 \times 3 + 1$。

排除法：B 是上取整；C 是浮点；D 无依据。

关联 · 向下取整（D1）：概念题代码化。

考点：向上取整输出（L2）。

解析：$(10 + 3 - 1) / 3 = 4$（4 袋：3+3+3+1）。正确答案 A。

实现要点：上取整公式 = (n + m - 1) / m。手算：$10 = 3 \times 3 + 1$，还需 1 袋。

排除法：B 是下取整（3 袋装不下）；C/D 无依据。

关联 · 向上取整（D2）：概念题代码化。

考点：模运算输出（L3）。

解析：$17 = 5 \times 3 + 2$ → 2。正确答案 A。

实现要点：余数 = a - (a / b) * b。手算：$17 \div 5$ 余 2。

排除法：B 是商；C 是模数；D 无依据。

关联 · 模运算的定义（D3）：概念题代码化。

考点：负数取模输出（L4）。

解析：(-7) % 3 = -1（C++ 符号随被除数）。正确答案 A。

实现要点：负数取模易错——需要数学余数时用 (x % m + m) % m。手算：$-7 = 3 \times (-2) - 1$。

排除法：B（2）是数学余数；C/D 无依据。

关联 · 负数取模（D4）：概念题代码化。