串联五讲知识，构建完整体系；直击真题痛点，锻造竞赛实力！
将前五讲的知识融会贯通，建立完整的数学基础认知框架。
| 类别 | 公式 | 备注 |
|---|---|---|
| GCD | GCD(a,b)=GCD(b,a%b) | O(log n)，Lamé定理 |
| LCM | a/GCD(a,b)*b | ⚠️ 先除后乘 |
| EXGCD | x=y', y=x'-⌊a/b⌋y' | 求逆元、解不定方程 |
| 逆元 | ((x%m)+m)%m | exgcd返回值可能为负 |
| P(n,m) | n!/(n-m)! | 连乘m个递减整数 |
| C(n,m) | n!/(m!(n-m)!) | = P(n,m)/m! |
| 杨辉递推 | C(n,m)=C(n-1,m-1)+C(n-1,m) | O(n²)预处理 |
| 卡特兰 | Cat(n)=C(2n,n)/(n+1) | 1,1,2,5,14,42... |
| 因数个数 | ∏(αᵢ+1) | n=∏pᵢ^αᵢ |
| 容斥(2集) | |A∪B|=|A|+|B|-|A∩B| | "至少一个" |
| R→10 | Σdᵢ×Rⁱ (秦九韶) | 从高位到低位迭代 |
| 10→R | 除基取余逆序排 | 先得低位后得高位 |
| 安全取模 | ((a%m)+m)%m | 保证结果∈[0,m-1] |
数学基础的各个知识点并非孤立存在，它们在题目中经常交叉出现：
汇总前五讲所有易错点，形成"错题免疫"能力。
7/2 = 3 不是 3.57.0/2-7%3 = -1 不是 2int a*b 可能超界long long(3-5)%7 = -2((3-5)%7+7)%7=5(a/b)%m ≠ (a%m)/(b%m)%m((x%m)+m)%mif(i%p[j]==0) break;i*i 开始a*b/gcd 先溢出a/gcd*b精选4道历年初赛/复赛真题，展示完整的审题→分析→求解→验证流程。
A. (170)₈ B. (174)₈ C. (200)₈ D. (164)₈
答案：B. (174)₈
考点：进制转换 + 整数运算。也可在八进制下直接算：7×4=34(八进制)=28(十进制)，写4进3；3×4+3=15(十进制)=(17)₈，拼接得174。
A. 570 B. 540 C. 560 D. 580
答案：A. 570。C(10,3) + C(10,1)×C(10,2) = 120 + 450 = 570。
本题核心方法：按奇偶分类 + 组合数 + 加法原理。
验证：GCD(30,36)=6 ✅, LCM(30,36)=30/6×36=180 ✅
考点：GCD×LCM=a×b 恒等式的直接应用。
A. 148 B. 156 C. 162 D. 171
答案：D. 171。核心方法是交换求和顺序——从"对每个数统计"变为"对每个质数统计贡献"。
考点：筛法思想 + 交换求和 + 质数分布。
从"会知识"到"能得分"，掌握数学题的系统化解题方法论。
以下模板建议在赛前默写熟练，考场上能快速调用：
| 模板名称 | 用途 | 复杂度 | 优先级 |
|---|---|---|---|
| GCD / __gcd | 最大公约数 | O(log n) | 必背 |
| EXGCD | 逆元、不定方程 | O(log n) | 必背 |
| 线性筛 | 批量求质数 | O(N) | 必背 |
| 组合数递推 | C(n,m) 预处理 | O(n²) | 必背 |
| 快速幂 | a^b mod m | O(log b) | 推荐 |
| 质因数分解 | 唯一分解 | O(√n) | 推荐 |
| Lucas定理 | 大组合数取模 | O(log_p n) | 选学 |
每个模板都给出完整可编译的实现，建议逐个敲一遍再默写。点击展开：
// 最大公约数：O(log n)，考场必背
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
// 最小公倍数：先除后乘防溢出
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}// 求 ax + by = gcd(a,b) 的一组解，O(log n)
long long exgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) { x = 1; y = 0; return a; }
long long g = exgcd(b, a % b, x, y);
long long t = x; x = y; y = t - a / b * y;
return g;
}
// 用途：求逆元——a 在模 m 下无逆元当且仅当 gcd(a,m) != 1
// 逆元 = (x % m + m) % m，其中 exgcd(a, m, x, y)// 批量求 1~n 的全部质数，O(N)，每个合数只被最小质因子筛一次
const int N = 1e7 + 5;
bool vis[N]; // vis[i]=true 表示合数
int primes[N], cnt = 0;
void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) primes[cnt++] = i; // i 是质数
for (int j = 0; j < cnt && (long long)i * primes[j] <= n; j++) {
vis[i * primes[j]] = true; // primes[j] 是 i*primes[j] 的最小质因子
if (i % primes[j] == 0) break; // 关键：保证线性
}
}
}// C(n,m) 预处理：O(n^2)，适用于 n <= 5000 左右、需要大量查询
const int N = 5005;
long long C[N][N];
const long long MOD = 1e9 + 7;
void init(int n) {
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; // 杨辉三角恒等式
}
}
// 使用：init(n) 后 C[n][m] 即为答案// 快速幂：O(log b)
long long qpow(long long a, long long b, long long m) {
long long res = 1;
a %= m;
while (b > 0) {
if (b & 1) res = res * a % m; // 当前二进制位是 1 就乘上
a = a * a % m; // 底数平方
b >>= 1;
}
return res;
}
// 费马小定理求逆元（m 为质数时）：inv(a) = qpow(a, m-2, m)// 唯一分解：O(sqrt(n))
void factorize(int n) {
for (int i = 2; (long long)i * i <= n; i++) {
if (n % i == 0) {
int e = 0;
while (n % i == 0) { n /= i; e++; }
cout << i << "^" << e;
if (n > 1) cout << " * ";
}
}
if (n > 1) cout << n << "^1"; // 剩下的大质因子
cout << endl;
}□ 数据类型是否够用？（int vs long long）
□ 模运算是否每步都取了模？
□ 减法取模是否加了 m 防负？
□ LCM 是否先除后乘？
□ 组合数是 P 还是 C？（有序vs无序）
□ 均分堆是否除了组数阶乘？
□ 线性筛是否有 break？
□ 质数判定是否排除了 1？
□ 边界 n=0, n=1 是否特判？
□ 数组大小是否开够？（+5 保险）
A基础 / B提高 / C挑战，覆盖全部六讲知识点，点击展开答案。
A. 20 B. 22 C. 24 D. 26
B. 22。1×16+0×8+1×4+1×2+0×1=22
考点：二进制转十进制按位权 2i 展开求和：5 位数的最高位权是 24=16，最低位权是 1。
易错：从最高位开始按 20 计权，或漏掉中间为 0 的位仍然占一个位权。
A. 6 B. 12 C. 18 D. 24
B. 12。36=2²×3², 48=2⁴×3, GCD=2²×3=12
考点：分解质因数后，GCD 取公共质因子的「最小指数」，与求 LCM 时取「最大指数」正好相对。
易错：把 GCD 误当 LCM 算成 144，或只挑出公共质因子 2、3 却忘了取最小的指数。
A. 336 B. 56 C. 24 D. 120
B. 56。8×7×6/(3×2×1)=336/6=56
考点：组合数可以用连乘形式计算：C(n,m) = n(n−1)…(n−m+1) 除以 m!，本质是「先按顺序取，再除以 m! 去序」。
易错：错用排列数 P(8,3)=336，忘记最后要除以 3!=6。
A. -5 B. 0 C. 3 D. 2
B. 0。(7-12)%5=-5%5=0, (0+5)%5=0。或直接：7-12=-5≡0(mod 5)
考点：负余数先由 C++ 规则算出，再「+5 后 %5」规范到 [0,4]；本题恰好整除，得到 0。
易错：以为 −5 % 5 的结果是 −5，或漏掉最外层还要再取一次模。
A. 1是最小的质数
B. 所有质数都是奇数
C. 2是唯一的偶质数
D. 质数有有限个
C。1非质非合；2是偶质数；质数无穷多。
考点：三条基础结论要记牢：1 既不是质数也不是合数；2 是唯一的偶质数；质数有无穷多个。
易错：把 1 当成最小的质数，或以为质数有上限、存在「最大的质数」。
A. 60 B. 180 C. 360 D. 540
B. 180。LCM(12,18)=36, LCM(36,30)=36/GCD(36,30)×30=36/6×30=180
考点：求多个数的最小公倍数可以两两递推，每一步都用 LCM(a,b) = a / GCD(a,b) * b。
易错：只算完前两个数的 LCM(36) 就收手，漏掉还要和第三个数 30 再求一次。
A. 48 B. 72 C. 96 D. 120
B. 72。插空法：先排其他3人(3!=6)，产生4个空位，甲乙插入C(4,2)×2!=12，6×12=72
考点：「不相邻」用插空法：先排其余元素造出空位，再把指定元素插入空位，避免去枚举「不相邻」的所有位置。
易错：用 5! = 120 减去相邻情况时算错，或忘记插入的两个空位有先后顺序、要乘 2!。
A. 2 B. 3 C. 4 D. 5
C. 4。恰好3个因数→p²形式(p为质数)。p²≤100→p≤10。质数2,3,5,7→4,9,25,49共4个。
考点：因数个数公式 (a+1)(b+1)… 等于 3 时，只能是「一个质数的平方」这一种形态，故只需找不超过 10 的质数。
易错：把 1 也算作一个候选，或忘了 11² = 121 已超出 100 而多算一个。
A. 4 B. 6 C. 8 D. 10
C. 8。(FF)₁₆=255=3×5×17，因数个数=(1+1)(1+1)(1+1)=8。255=3¹×5¹×17¹，因数个数=2×2×2=8。答案为C. 8。
考点：综合性解法是先做进制转换把 (FF)16 化成十进制 255，再质因数分解，最后套用因数个数公式。
易错：看到 255 就误判为质数，漏掉 255 = 3 × 5 × 17 这一步分解。
A. 3 B. 5 C. 8 D. 11
C. 8。5×8=40≡1(mod 13)。验证：40-3×13=40-39=1 ✅
考点：乘法逆元由定义式 a × x ≡ 1 (mod m) 确定，模数较小时逐一试乘 1~12 即可找到唯一解。
易错：把逆元当成 1/5，或把 −5 ≡ 8 (mod 13) 与「5 的逆元」混为一谈——两个概念不同。
A. 4 B. 6 C. 7 D. 8
C. 8
x+y=20, x (1,19)✅(3,17)✅(7,13)✅(9,11)✅ → 只有4对？ 重新枚举：x=1,3,7,9时GCD=1。x=2→GCD(2,18)=2❌, x=4→GCD(4,16)=4❌, x=5→GCD(5,15)=5❌, x=6→GCD(6,14)=2❌, x=8→GCD(8,12)=4❌ 实际只有4对。若选项无4，题目条件可能有调整。核心方法：枚举+GCD判定。 考点：先由 x + y = 20 判定 x、y 同奇偶，缩小候选范围，再对每个候选逐一求 GCD 是否为 1。 易错：忽略「和为偶数则两数同奇偶」，把 x=1~9 的对都当成互质来数；注意两数同为偶数时 GCD 至少为 2。
A. 21 B. 28 C. 36 D. 56
B. 28。隔板法（可重组合）：C(6+3-1, 3-1)=C(8,2)=28
考点：相同物品分给不同盒子、允许空盒，用隔板法：n 个球 k 个盒的方案数为 C(n+k−1, k−1)。
易错：误用 36 = 729，那是「球互不相同、盒子不同」的情形，本题球是相同的。
A. 8 B. 14 C. 16 D. 24
B. 14。Cat(4)=C(8,4)/5=70/5=14
考点：出入栈序列数是卡特兰数的典型应用，Cat(n) = C(2n,n)/(n+1)，注意分母是 n+1 而不是 n。
易错：把答案记成 C(8,4) = 70，忘记还要除以 n+1 = 5。
A. 0 B. 1 C. 2 D. 24
A. 0。2¹⁰⁰只含质因子2，不含5，所以末尾没有0。末尾零的个数=min(2的幂次, 5的幂次)，这里5的幂次=0。
考点：十进制末尾零的个数等于「质因数 2 的个数」与「质因数 5 的个数」中较小的那个，因为 10 = 2×5。
易错：以为幂次很高就会有很多 0，忽略了 2100 中完全没有质因子 5，无法凑出 10。
A. 28 B. 56 C. 70 D. 120
B. 56。8个位置选3个放1：C(8,3)=8×7×6/6=56
考点：「恰好含 3 个 1」等价于从 8 个位位置中选 3 个放 1，其余放 0，是标准的组合问题。
易错：以为最高位是符号位要排除，其实题目说「8 位二进制数」时 8 个位置全部可用；也不要用排列数 P(8,3)。