专题19 · 数学专题2
本讲四块：加法原理与乘法原理、排列与组合、同余与取模、素数筛法。
前三块决定你会不会数数，最后一块决定你数得快不快。
两道真题：素数个数（线性筛）、组合数取模（杨辉三角）。
什么时候加，什么时候乘
加法原理（分类）
做一件事有若干类互不重叠的方法，每类分别有 m₁、m₂ … 种 → 总数 = m₁ + m₂ + …
例：北京到上海，飞机 3 班 + 高铁 5 班 + 大巴 2 班 = 10 种。
乘法原理（分步）
做一件事要分几步完成，每步分别有 m₁、m₂ … 种 → 总数 = m₁ × m₂ × …
例：上衣 4 件 × 裤子 3 条 × 鞋 2 双 = 24 套。
最常犯的错：把"分步"当成"分类"相加，或者把"分类"当成"分步"相乘。
同一件事，加法还是乘法
唯一的区别：有没有顺序
排列 A(n, r)：有序
从 n 个不同元素里取 r 个排成一列。
A(n,r) = n! / (n−r)! = n×(n−1)×…×(n−r+1)
例：5 人选正、副班长 → A(5,2) = 20（张三正/李四副 ≠ 李四正/张三副）。
组合 C(n, r)：无序
从 n 个不同元素里取 r 个凑成一组，不分先后。
C(n,r) = A(n,r) / r! = n! / (r!·(n−r)!)
例：5 人选 2 人组队 → C(5,2) = 10（两人一组，无正副之分）。
两条必须记住的性质
① C(n,r) = C(n,n−r) —— 选 r 个留下 = 选 n−r 个丢掉，可用来把 r 缩小一半。
② C(n,r) = C(n−1,r) + C(n−1,r−1) —— 杨辉三角，也是组合数 DP 求法的基础。
含义：面对第 n 个元素，不选它（前 n−1 个里选 r 个）或 选它（前 n−1 个里再选 r−1 个），两类互斥 → 加法。
为什么组合要除以 r!
C(n,r) = 上 + 左上
边算边取余，别等最后
同余的定义
若 a % m == b % m，称 a 与 b 模 m 同余，记作 a ≡ b (mod m)。
性质：自反、对称、传递。
运算可"先取余再算"
(a + b) % m = (a%m + b%m) % m
(a × b) % m = (a%m × b%m) % m
所以可以每一步都取余，结果不变。
为什么必须边算边取余
组合数、阶乘、大数乘法增长极快：100! 有 158 位，任何整数类型都放不下。
但如果我们只关心它对 m 的余数，就可以每乘一次就取一次余，数字永远不超过 m。
这就是"大数乘法取模"类题目的唯一解法。
long long ans = 1;
for (int i = 1; i <= n; i++) ans = ans * i % MOD; // 每步取余(a - b + MOD) % MOD；
② a × b 本身在取余前就可能溢出 long long → 用更大的类型或先分解。三种筛法，一个比一个聪明
① 普通（逐个试除）
对每个数独立判定是否质数。
复杂度 O(n√n)。
n = 10⁵ 时约 3×10⁷ 次 → 勉强/超时。
② 埃氏筛
从 2 开始，把每个质数的倍数划掉。
复杂度 O(n log log n)。
缺点：合数会被重复划（如 12 被 2 和 3 各划一次）。
③ 线性筛（欧拉筛）
让每个合数只被最小质因子划一次。
复杂度 O(n)。
关键：if (i % p == 0) break;
for (int i = 2; i <= n; i++){
if (!isComp[i]) primes.push_back(i); // 没被划掉 → 质数
for (int p : primes){
if ((long long)i * p > n) break; // 超范围就停
isComp[i * p] = true;
if (i % p == 0) break; // ★ 保证只用最小质因子筛
}
}
p 能整除 i 时，说明 p 是 i 的最小质因子，
后续更大的质数再去筛 i*p' 时，该合数的最小质因子仍是 p，会被重复筛 → 必须停。数一数每个合数被划了几次
每乘一次就取一次余
本讲五个高频失分点
① 加法乘法混用
❌ 把分步当分类相加。
✅ "要么…要么…"→加；"先…再…"→乘。
② 排列组合搞混
❌ 该除以 r! 却没除（把组合当排列）。
✅ 问自己"交换顺序算不算同一种"。
③ 最后才取模
❌ 先算出 100! 再取模 → 溢出。
✅ 每步取余。
④ 线性筛漏 break
❌ 缺 if (i % p == 0) break; → 退化成埃氏筛。
✅ 必须有。
知识树
数学2 ─┬─ 计数原理：加法（分类）/ 乘法（分步）
├─ 排列 A(n,r) 有序 ／ 组合 C(n,r) 无序（÷ r!）
├─ 同余：边算边取余
└─ 筛法：试除 O(n√n) → 埃氏 O(n log log n) → 线性 O(n)
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
素数个数 · PRIMECNT
第1档 · 2 分钟n < 2 → 0
第2档 · 8 分钟
对每个数试除到 √i，n ≤ 10⁴ 稳过
第3档 · 10 分钟
只判奇数（除 2 外全是合数）
第4档 · 15 分钟
埃氏筛 / 欧拉筛，O(n log log n)
组合数（取模） · COMBINE
第1档 · 2 分钟m == 0 或 m == n → 1；m > n → 0
第2档 · 8 分钟
用 C(n,m) = C(n−1,m−1) + C(n−1,m) 递推，n ≤ 1000 稳过
第3档 · 10 分钟
模数是质数且 n ≤ 2000 → 杨辉三角递推就够
第4档 · 15 分钟
阶乘 + 逆元（费马小定理）：fac[n]·inv(m)·inv(n−m) % MOD
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。