如果你曾经卡在一道要求给出“对一个大素数取模”后答案的竞赛题上，那么你其实已经与竞赛编程中的数论正面打过照面了。
数论研究的是整数：整除性、素数、余数，以及连接它们的那些出人意料的规律。在 美国计算机奥林匹克竞赛（USACO） 这类比赛以及众多在线评测系统中，这些思想反复出现，常常伪装在计数问题、几何或组合数学之中。好消息是，核心工具箱并不大，既学得会又有回报。掌握它能让学生在更高难度的分组中获得稳定的优势。
数论在竞赛中为何重要
大多数编程竞赛要求你计算精确的整数答案，而这些答案可能会膨胀到天文数字。为了让结果保持在 64 位整数范围内，题目常常要求给出答案对一个固定素数（例如 1,000,000,007）取模后的值。仅这一个要求就牵涉出一整套技巧：模加法、模乘法、模幂运算以及模除法。数论同时也是计数的语言，因此组合数学问题非常依赖它。
具体到 USACO，数论往往出现在 Silver 和 Gold 分组中，模运算和最大公约数在那里成为标准工具。随着学生向 Platinum 和国际信息学奥林匹克竞赛迈进，这些思想会更加深入，但根基始终不变。这正是我们在 竞赛编程课程 中把这部分内容作为核心课程的原因。
必备工具箱
你不需要修一门大学课程才能上手。下面这些基础模块涵盖了绝大多数竞赛场景：
最大公约数（GCD）与欧几里得算法
欧几里得算法通过不断用余数替换较大的数，在大约 O(log min(a, b)) 的时间内求出两个整数的 GCD。它的“近亲”——扩展欧几里得算法，则能找到满足 ax + by = gcd(a, b) 的整数 x 和 y。这一扩展是求解线性方程和计算模逆元背后的主力。
素数与埃拉托斯特尼筛法
埃拉托斯特尼筛法通过标记每个素数的倍数，在约 O(n log log n)（接近线性）的时间内列出不超过 n 的所有素数。基于这个筛法，你可以构建快速的素因数分解，并预处理出某个区间内每个数的最小素因数——这一技巧能把许多“给这个数分解因数”的子问题变成瞬间查表。
模运算与快速幂
用余数进行运算，能让数字保持较小，同时对加法、减法和乘法保持正确性。要高效计算 a^b mod m，可使用二进制（快速）幂，它通过反复平方在 O(log b) 内完成。这一个例程出现在极大比例的中高难度题目中。
模逆元与计数
在模运算下，除法是个棘手的操作。当模数为素数 p 时，费马小定理指出：对于任意不被 p 整除的 a，有 a^(p-1) 同余于 1（mod p），因此 a 的逆元就是 a^(p-2) mod p。配合预处理好的阶乘，这能让你快速计算二项式系数“n 选 r”对素数取模的结果，而这正是无数组合数学任务的支柱。
一个行之有效的学习顺序是：先 GCD，再筛法，然后是模运算与快速幂，最后是模逆元与组合数学。每一步都会复用前一步的内容。
值得逐步进阶的主题
一旦这些必备内容变得驾轻就熟，下面这些中级思想能进一步拓展你的能力边界：
- 欧拉函数 φ(n)：统计不超过 n 且与 n 互素的整数个数，是欧拉定理的基础——欧拉定理把费马的结论推广到了非素数模数。
- 中国剩余定理（CRT）：根据一个数对若干两两互素的模数所得的余数来重建这个数，当没有一个足够大的素数可用时很有用。
- 线性筛：一种能在线性时间内于某区间上计算积性函数的筛法变体。
数论奖励善于识别规律的人。同样的五六个工具会以新的“装扮”反复出现，因此在经典题目上有针对性地刻意练习，胜过死记几十种边界情况。
如何高效练习
只有动手实现，理论才能真正记牢。每个算法至少从零手写一遍，然后做按难度分级的题集——在把概念混合之前，先逐个隔离地练习单一概念。像 USACO Guide 这样精选的进阶题单会按主题和难度组织题目，我们的 博客 也会分享更多学习策略。由于竞赛形式会不断演变，请始终以官方竞赛网站为准核对当前的赛制、分组和参赛资格，而不要只依赖任何单篇文章。
数论是年轻选手所能做出的回报最高的投资之一：一组精炼的思想就能解锁横跨算法、数学和信息学的诸多问题。如果你的孩子已准备好在有结构的辅导与反馈中打下这一基础，欢迎了解我们的 竞赛编程课程，即刻开始。