第 15 章 · 竞赛数学进阶

数论是提高级笔试和上机的常客：快速幂、筛法、扩展欧几里得、逆元、组合数，还有入门博弈论。

学习目标

• 掌握快速幂，理解取模运算规则 \((a \times b) \bmod p\)
• 掌握埃氏筛与线性筛
• 理解扩展欧几里得算法，会求逆元
• 会用递推和公式求组合数（杨辉三角）
• 了解简单组合博弈（NIM 游戏、必胜态分析）

课程规划（编写中）

• 快速幂与取模运算
• 素数筛法
• 扩展欧几里得与逆元
• 组合数学
• 博弈论入门

为什么到处取模

竞赛里大数答案往往要求 mod 1e9+7 输出——数论工具链就是为此准备的，本章会反复用到。