1. 项目概述一本写给竞赛选手的数论实战手册如果你正在准备ACM-ICPC、信息学奥赛OI或者数学奥赛MO并且对“同余”这个概念感到既熟悉又头疼——熟悉是因为它无处不在头疼是因为那些变幻莫测的模方程和需要灵光一现的构造——那么你手上正缺的很可能就是这样一份材料。这不是一本高高在上的数学教科书而是一本完全从竞赛实战角度出发用十五万字符打磨出来的“同余”专题攻坚指南。它的核心目标非常明确剥开同余理论那些严谨但略显枯燥的数学外衣直击算法竞赛中那些高频、核心且富有技巧性的考点与应用。我见过太多选手他们能熟练背诵费马小定理、欧拉定理的公式但遇到一个需要自己构造同余式来证明整除关系或者利用中国剩余定理CRT合并模方程的实际赛题时思路就卡壳了。问题往往不在于理论本身而在于缺乏在竞赛高压环境下快速、准确地将理论转化为解题武器的“手感”。这份材料要解决的正是这个“最后一公里”的问题。它假设你已经了解同余的基本定义a≡b (mod m)然后迅速带你进入竞赛的深水区重点剖析模运算的性质、线性同余方程、逆元、中国剩余定理、高次同余方程包括离散对数这些必考内容并通过大量精选的竞赛真题和模拟题训练你条件反射般的解题思维。无论是希望夯实数论基础的OI新人还是需要在ACM赛场上快速切掉数论题的资深队员都能从中找到针对性的训练价值和思维提升。2. 内容整体设计与思路拆解为什么“同余”值得一个十五万字的专题很多竞赛入门数论资料会把“同余”作为一章用二三十页的篇幅讲完。但这本手册选择用十五万字的体量来深挖其设计思路源于对竞赛命题趋势的深刻洞察。在当前的算法竞赛中数论题目早已不再是简单的“套公式”计算。命题人热衷于考察选手对同余概念的灵活运用和创造性构造能力。一个题目可能表面上是数据结构或动态规划但关键的优化步骤却依赖于一个精巧的同余性质一个看似复杂的计数问题通过建立合适的同余模型可以瞬间化为简单的模运算。2.1 核心设计逻辑从“知识节点”到“解题网络”传统的学习路径是线性的学习定义→学习定理→学习例题。这本手册的设计是网状的。它以“同余”为核心节点但每一个延伸出去的定理和应用都会立刻与竞赛中的典型场景、常见技巧和易错点相连接。例如在讲解“模意义下的乘法逆元”时绝不会仅仅停留在介绍扩展欧几里得算法exgcd求逆元。它会立刻拆解场景识别什么情况下需要用到逆元通常是除法取模如组合数C(n, m) mod p的计算。方法对比exgcd是通用方法但当模数p为质数时费马小定理a^(p-2)更高效。手册会通过复杂度分析和代码实现对比让你清楚在不同数据范围p是否可达10^9级别下的选择策略。预处理优化竞赛中经常需要频繁使用逆元如何用O(n)的时间预处理1到n所有数的逆元这里会引入线性递推公式inv[i] (p - p/i) * inv[p%i] % p并详细推导其原理这是实战中大幅提升效率的关键技巧。边界与陷阱a与模数m不互质时逆元不存在在代码中如何安全地判断和处理这是很多新手容易忽略导致WA错误答案的点。这样的设计使得每一个知识点都不是孤立的而是嵌入到一个完整的“解题工具箱”中。学习的过程就是在编织一个针对数论问题的“条件反射”网络。2.2 内容编排的竞赛导向性全书的内容取舍和深度控制严格以竞赛真题为标尺。对于一些在纯数学中很重要但在竞赛中极少出现的冷门定理只会简要提及。相反对于竞赛“宠儿”则会不吝篇幅。重中之重中国剩余定理CRT及其扩展。这不仅是必考考点更是解决一类“模数非质数”或“模数巨大”问题的核心思想。手册会从最简单的孙子问题讲起逐步推导到CRT的标准形式并立刻升级到更实用的“扩展中国剩余定理”ExCRT用于处理模数不一定两两互质的更一般情况。这里会重点讲解如何通过合并两个同余方程x ≡ a1 (mod m1)和x ≡ a2 (mod m2)来递归求解并分析解的存在性条件gcd(m1, m2) 必须能整除 (a2 - a1)。这部分会配有大量练习让你熟练掌握合并方程的过程。攻坚难点高次同余与离散对数。当问题上升到求解a^x ≡ b (mod p)时就进入了竞赛数论的深水区。手册会系统介绍BSGS大步小步算法及其扩展算法这是解决离散对数问题的利器。不仅讲算法步骤更会讲清楚其“分块”思想的本质将x表示为i*m j的形式以及如何通过哈希表或C中的unordered_map来优化查找。对于模数p为质数、合数等不同情况下的变种和注意事项也会有专门章节讨论。技巧聚合同余在证明与构造中的应用。这是拉开顶尖选手差距的地方。手册会专题讲解如何用同余来证明整除性、分析数的性质如平方数的模特性、构造满足特定条件的序列或函数。例如证明n^5 - n能被30整除通过分别模2, 3, 5并结合中国剩余定理可以非常优雅地解决。这类技巧需要大量的例题来感悟手册会提供丰富的“弹药”。3. 核心细节解析与实操要点逆元、CRT与欧拉定理的竞赛化理解3.1 乘法逆元不止于“求”更在于“用”和“优化”求逆元是基础操作但竞赛中更考验你能否在复杂场景下高效、正确地使用它。核心要点一逆元的存在性与快速判断在代码中特别是在处理多组输入或动态数据时不能默认逆元存在。安全的做法是在使用扩展欧几里得算法求逆元时同时检查返回值即gcd(a, m)是否为1。如果非1则逆元不存在需要采用其他数学处理或题目保证数据合法。// 扩展欧几里得算法返回 gcd(a, b)并求解 ax by gcd(a, b) int exgcd(int a, int b, int x, int y) { if (!b) { x 1; y 0; return a; } int d exgcd(b, a % b, y, x); y - a / b * x; return d; } // 求 a 在模 m 下的逆元不存在则返回 -1 int mod_inv(int a, int m) { int x, y; int d exgcd(a, m, x, y); if (d ! 1) return -1; // a 和 m 不互质逆元不存在 return (x % m m) % m; // 调整到 0~m-1 范围内 }核心要点二线性递推求逆元的原理与实现当需要用到1到n所有数的逆元时常见于预处理组合数线性递推算法将复杂度从O(n log n)降至O(n)。其原理基于模运算的等式推导 设p k * i r(其中k p / i,r p % i)则有k * i r ≡ 0 (mod p)。 两边乘以i^(-1) * r^(-1)得到k * r^(-1) i^(-1) ≡ 0 (mod p)。 因此i^(-1) ≡ -k * r^(-1) (mod p)。 由于r p % i i当按顺序计算时inv[r]已经求得从而可以递推得到inv[i]。const int MOD 1e97; const int N 1e65; int inv[N]; void pre_inv() { inv[1] 1; for (int i 2; i N; i) { inv[i] (MOD - MOD / i) * 1LL * inv[MOD % i] % MOD; // 注意乘法可能溢出用1LL提升为long long } }注意此方法要求模数MOD为质数且需要预处理的N小于MOD。这是竞赛中的常见场景。3.2 中国剩余定理CRT从“知其然”到“知其所以然”很多选手会背CRT的公式但一旦模数不互质ExCRT或者需要自己推导合并过程就束手无策。手册会强调理解“合并”的本质。核心思想解一组同余方程x ≡ a_i (mod m_i)本质是寻找一个x使其对所有i都满足x a_i k_i * m_i。CRT的核心操作是两两合并。合并两个方程的详细推导 假设我们已经得到前k-1个方程的一个解x且当前模数为M lcm(m1, m2, ..., m_{k-1})。现在要加入第k个方程x ≡ a_k (mod m_k)。 我们需要寻找一个t使得新的解x x t * M满足第k个方程即x t * M ≡ a_k (mod m_k)t * M ≡ a_k - x (mod m_k)。 令d gcd(M, m_k)。这个线性同余方程有解的条件是d | (a_k - x)。 如果有解我们可以用扩展欧几里得算法求解t然后得到新的解x x t * M新的模数更新为M lcm(M, m_k) M / d * m_k。实操要点解的存在性判断在每次合并时都必须检查gcd(当前模数, 新模数)是否能整除(新余数 - 当前解)。如果不能则整个方程组无解。防溢出处理在计算t * M和更新M时数值可能非常大需要使用64位整数long long并在乘法时配合取模操作或者使用快速乘龟速乘算法来避免中间结果溢出。最终解的形式合并完成后得到的x是模M意义下的一个特解。通解为x k * M(k为任意整数)。题目通常要求最小正整数解即(x % M M) % M。3.3 欧拉定理与费马小定理幂运算降维的利器在竞赛中欧拉定理a^(φ(m)) ≡ 1 (mod m)(当gcd(a, m)1) 及其特例费马小定理m为质数时φ(m)m-1最主要的应用是简化模意义下的幂运算。经典场景计算 a^b mod m其中 b 非常大直接快速幂的复杂度是 O(log b)但当 b 大到无法存储比如是一个有1000位的十进制数时我们需要利用欧拉定理。如果gcd(a, m) 1我们可以利用a^b ≡ a^(b mod φ(m)) (mod m)来将指数b缩小到φ(m)的范围内。如果gcd(a, m) 1情况更复杂需要用到扩展欧拉定理。这是竞赛中的一个高级考点手册会详细讨论其条件当b ≥ φ(m)时a^b ≡ a^(b mod φ(m) φ(m)) (mod m)。实操中的关键步骤计算 φ(m)需要分解质因数。如果 m 很大但查询次数多可能需要预处理。处理大指数 b以字符串或大数形式读入 b一边读入一边计算b mod φ(m)同时判断 b 是否大于等于 φ(m)用于扩展欧拉定理。最后用快速幂计算用缩小后的指数进行标准的快速幂运算。// 假设已计算得到 phi_m (φ(m))且判断了是否需要加 phi_m (根据扩展欧拉定理) long long huge_mod(string b_str, long long phi_m) { long long b_mod 0; bool large false; // 标记b是否phi_m for (char c : b_str) { b_mod (b_mod * 10 (c - 0)) % phi_m; // 在计算过程中可以同时判断原数b是否phi_m这里简化处理 } // 根据扩展欧拉定理如果bphi_m且gcd(a,m)!1则最终指数应为 b_mod phi_m // 否则最终指数为 b_mod return b_mod; // 这里返回的是简化后的指数 }4. 实操过程与核心环节实现攻克一道典型的同余综合题让我们通过一道融合了逆元、CRT和模幂运算的竞赛题来串联整个实操过程。假设题目如下求最小的正整数x满足x ≡ 2 (mod 3)x ≡ 3 (mod 5)x ≡ 2 (mod 7)x^1234567890123456789 ≡ 5 (mod 11)注模数11是质数步骤1处理线性同余方程组123这是一个标准的中国剩余定理问题模数3,5,7两两互质。设M 3*5*7 105M1 35,M2 21,M3 15。分别求逆元t1 inv(35) mod 3即35 * t1 ≡ 1 (mod 3)。因为35 mod 3 2所以是2 * t1 ≡ 1 (mod 3)得t1 2因为2*24≡1 mod 3。同理t2 inv(21) mod 521 mod 5 1所以t2 1。t3 inv(15) mod 715 mod 7 1所以t3 1。计算特解x0 (2*35*2 3*21*1 2*15*1) mod 105 (140 63 30) mod 105 233 mod 105 23。通解为x 23 105k。步骤2处理高次同余方程4方程是x^E ≡ 5 (mod 11)其中E 1234567890123456789模数p11是质数。首先由于模数是质数所有非零元都有逆元。我们需要解这个离散对数问题。但注意x本身也是未知的且需要满足步骤1的条件。因此我们需要遍历步骤1解的形式x 23 105k并检查哪个满足方程4。直接遍历k不可行因为指数E巨大。这里需要用到费马小定理对于任意x不被11整除有x^(10) ≡ 1 (mod 11)。因此我们可以将指数E对10取模来简化。计算e E mod 10。1234567890123456789的个位数是9所以e 9。实际上因为10的循环节只需看个位。方程简化为(23 105k)^9 ≡ 5 (mod 11)。因为模数11很小我们可以遍历k 0, 1, 2, ..., 10因为x mod 11的值会循环。计算每个x (23 105k) mod 11然后计算x^9 mod 11看是否等于5。计算过程k0:x23 mod 11 1-1^91不等于5。k1:x128 mod 11 128-11*11128-1217-7^9 mod 11。7^249≡5,7^4≡5^225≡3,7^8≡3^29,7^97^8*7≡9*763≡8不等于5。k2:x233 mod 11 233-11*21233-2312-2^9512 mod 11。2^532≡10,2^92^5*2^4≡10*16160≡160-11*14160-1546不等于5。k3:x338 mod 11 338-11*30338-3308-8^9 mod 11。8^264≡9,8^4≡9^281≡4,8^8≡4^216≡5,8^98^8*8≡5*840≡7不等于5。k4:x443 mod 11 443-11*40443-4403-3^9 mod 11。3^327≡5,3^9(3^3)^3≡5^3125≡125-11*11125-1214不等于5。k5:x548 mod 11 548-11*49548-5399-9^9 mod 11。9≡ -2(-2)^9 -512 ≡ -51211*47 -5125175。成立所以当k5时x 23 105*5 23 525 548满足方程4。步骤3验证与得出最终答案x548满足548 mod 3 2✔548 mod 5 3✔548 mod 7 2✔548^E mod 11经计算等于5 ✔ 因此最小的正整数解就是548。这道题综合了CRT求基础解、费马小定理简化大指数、以及小范围枚举验证的技巧。在实战中枚举k的范围可以进一步优化因为x mod 11的值只取决于(23 105k) mod 11而105 mod 11 6所以实际上是遍历(23 mod 11) 6k mod 11即1 6k mod 11k从0到10即可覆盖所有可能。5. 常见问题与排查技巧实录避开同余路上的那些“坑”即使理解了原理在竞赛编码实现中依然会踩到各种各样的坑。下面记录了一些典型问题和排查思路。5.1 逆元计算相关问题1求逆元时得到负数或错误结果。排查检查扩展欧几里得算法是否正确实现了ax by gcd(a,b)的求解特别是递归返回后x, y的更新步骤。确保最终对返回的x进行了(x % m m) % m的正规化处理。技巧在调试时可以手动验证(a * inv_a) % m是否等于1。问题2使用费马小定理求逆元a^(m-2)时超时或溢出。排查模数m是否真的是质数如果m不是质数费马小定理不适用。即使m是质数当m很大如1e97时计算a^(m-2)需要使用快速幂算法O(log m)并确保在乘法过程中使用long long或配合取模防止溢出。技巧对于固定的质数模数可以预先用快速幂写好求逆元函数。对于需要大量逆元的情况优先使用线性递推预处理。5.2 中国剩余定理CRT相关问题1合并方程时解越来越大导致整数溢出。排查这是实现ExCRT时最常见的问题。在计算t * M和更新M lcm(M, m_i)时即使使用long long乘积也可能超过64位范围。解决方案使用快速乘又称“龟速乘”来计算(t * M) % new_M。其原理与快速幂类似将乘法转化为加法在加法的每一步进行取模。// 快速乘 (计算 a*b % mod)防止溢出 long long quick_mul(long long a, long long b, long long mod) { long long res 0; a % mod; while (b) { if (b 1) res (res a) % mod; a (a a) % mod; b 1; } return res; } // 在ExCRT合并步骤中使用 // x x quick_mul(t, M, M_new); // 更新解 // M M / d * m_i; // 更新模数注意先除后乘防溢出问题2判断方程组无解的条件把握不准。排查在ExCRT的每次合并中必须检查gcd(当前模数 M, 新模数 m_i)是否能整除(新余数 a_i - 当前解 x)。不能只检查最后一次每次合并都要检查。技巧将检查逻辑直接嵌入合并函数中一旦发现(a_i - x) % d ! 0立即返回无解标志。5.3 幂取模与欧拉定理相关问题1使用欧拉定理降指数时忽略了a与m不互质的情况。排查这是应用扩展欧拉定理时最容易出错的地方。务必先计算gcd(a, m)。如果等于1直接使用a^(b mod φ(m))如果大于1则必须判断指数b是否大于等于φ(m)以决定是否需要在b mod φ(m)的基础上加上φ(m)。技巧在读入大指数b字符串形式时可以同时完成两件事1) 计算b mod φ(m)2) 判断b的数值是否大于等于φ(m)。用一个布尔变量flag来记录。问题2计算大数幂取模时即使用了快速幂也超时。排查检查指数b的大小。如果b是正常整数1e9快速幂的O(log b)是很快的。如果超时很可能是因为在循环中频繁调用快速幂或者模数m很大导致乘法操作变慢。优化对于需要多次计算同一底数a的不同次幂的情况可以考虑预处理a的幂次表。对于模数固定且运算量极大的情况可以研究蒙哥马利乘法等更底层的优化但这在竞赛中较少见通常优化算法本身是更有效的途径。5.4 综合与思维类问题问题1如何想到用同余来证明或构造经验当题目中出现“整除”、“余数”、“周期性”、“循环节”、“平方数”、“立方数”等关键词时应优先考虑同余。对于证明整除a|b可以尝试证明b ≡ 0 (mod a)。对于寻找具有某种性质的数可以尝试枚举模某个数的余数利用余数的有限性进行筛选或反证。经典案例证明任何完全平方数模4只可能是0或1。通过枚举x mod 4的所有可能0,1,2,3计算x^2 mod 4发现结果只能是0或1。这个结论经常用于证明某个数不是完全平方数。问题2面对复杂的同余方程组无从下手。策略尝试化简或转换。有时可以通过变量替换如令y x c来简化方程。对于模数不是质数的方程考虑分解模数为质数幂然后分别求解利用中国剩余定理升维。对于高次方程可以尝试利用原根、指标离散对数将其转化为线性问题或者利用模数的特殊性如小模数直接枚举。心态同余问题往往需要一些“试探”和“观察”。从小的模数或特殊情况入手寻找规律是竞赛中解决数论问题的有效方法。这本十五万字的手册正是通过大量的例题和练习来帮助你积累这种“试探”的经验和“观察”的直觉。