数论是 ACM 国际大学生程序设计竞赛中的重要数学

质数与筛法是数论在竞赛中的基础模块。质数定义为大于1且只有1和自身两个正因数的自然数。若要判断一个数是否为质数，最直接的办法是从2一直试除到平方根，但在大规模场景下需要高效的判定策略。核心要点包括：若一个数存在非平凡因子，则最小的那个因子必不超过平方根，因此只需在区间[2, floor(sqrt(n))]内搜索即可做出准确判断。这一思想是后续所有优化算法的数学基础，能将判定复杂度从线性降至平方根数量级，尤其在处理接近十亿量级的大整数时，效果尤为显著。

为在大范围内快速获得质数集合，常用筛法是埃拉托斯特尼筛法。其核心思想是从小到大遍历未筛过的数，若当前数未被标记为合数，则它是质数，并将其所有倍数标记为合数。如此持续到处理到平方根的范围，未被标记的数即为质数。埃拉托斯特尼筛法的时间复杂度通常为 O(N log log N)，远优于单纯的逐个试除法。实际实现中可通过布尔数组记录状态，并在内存受限时采用位压缩、分段筛等技巧来降低空间需求，必要时也可结合分段筛来处理更大区间。

除了常规筛法，线性筛（又称欧拉筛）通过引入每个数的最小质因子，使得每个合数仅被筛一次，时间复杂度达到 O(N)。该方法不仅能高效生成质数表，还能同步输出与乘法结构相关的其他数论函数，如莫比乌斯函数、欧拉函数等，适用于需要同时获得多种数论信息的题型。

模运算是数论在计算中的另一大支柱。模运算将数系映射到有限域的等价类上，强调通过同余关系来进行算术运算yy易游。基本概念包括：若 a、b、m 为正整数，若 a 与 b 之差能被 m 整除，则 a 与 b 在模 m 下同余，记作 a ≡ b (mod m)。同余关系具备自反性、对称性、传递性，能将整数分成 m 个互不相交的剩余类，形成模 m 的剩余系。

在编程实现中，模加、模乘、模幂等运算需处理溢出与高效性问题，通常采用快速幂（指数分解为二进制的乘方）来实现 O(log n) 的幂模运算。快速幂通过二分法逐步把大指数变成若干次平方与乘法的组合，极大提升运算效率。对于更大规模的指数或模数，需结合高效的模乘实现以避免中间结果超出机器整数范围。

在模运算的扩展中，理解同余的逆元概念非常关键。若 gcd(a, m) = 1，则存在唯一的模乘逆元 a 的乘法逆元，使 a·a^{-1} ≡ 1 (mod m)。求逆元常用扩展欧几里得算法，若模数为素数，还可使用费马小定理简化为 a^{m-2} mod m。这些工具是后续扩展欧几里得与中国剩余定理的重要前提。

中国剩余定理（CRT）提供在模数两两互质的情况下将一组同余方程合并为一个等价的单一方程的强大方法。更进一步，当模数不两两互质时，需采用广义 CRT 进行合并，逐步将多组同余方程拼接成一个通解形式，再在给定上界内统计解的个数。这一链路在解密、编码理论、密码学与竞赛题解中均有广泛应用。

在课程的高级部分，将引入同余工具在更广泛场景中的应用。例如：通过模运算建立对等价类的理解，结合矩阵快速幂解决递推关系，利用二进制拆解实现快速幂，以及在密码学与哈希设计中的实际应用。还将讨论常见题型的解题思路，如周期性现象、循环节（Pisano 周期）、以及逆元存在性判定等，帮助在比赛中快速建模并选取高效模板。

实战策略与题型辨析方面，竞赛题往往呈现“看似简单实则陷阱密布”的特点。常见命题模式包括周期性现象、模逆元存在性判断以及基于唯一分解定理的因子计数等。通过对数据范围和输入特征的观察，可以判断应选择试除、筛法、快速幂、Pollard-Rho 与 Miller-Rabin 等不同工具的组合；对于多组同余方程，CRT 的应用往往是核心路径。面对大整数或高难度的因数分解题，Miller-Rabin 结合 Pollard-Rho 的组合成为解决此类题目的主流方法；而在需要处理非互质模数的方程组时，广义 CRT 提供了可行的合并策略。

总结而言，掌握质数判定、筛法、模运算、快速幂、同余与 CRT 的系统方法，能帮助选手在 ACM 题目中快速定位核心模块，正确选择算法路径，并将理论知识高效转化为可执行的高性能代码。这一数论工程链条不仅支撑竞赛题解，也奠定了现代信息安全与密码学理论的基石。