1. 从“余数”到“同余”算法竞赛中的思维跃迁如果你在算法竞赛无论是ACM、OI还是NOI中刷过一些数论题可能会发现一个有趣的现象很多题目描述里最终答案往往要求对一个很大的数取模比如1e97。新手可能会觉得这只是为了防止答案过大而溢出一个简单的技术性操作。但当你真正深入数论的世界尤其是接触到“同余”这个概念后你会恍然大悟——取模不是终点而是一扇通往全新数学世界的大门。这个世界的语言就是同余。我刚开始打比赛时对同余的理解也仅限于a % b这个操作。直到在解决一道关于“循环节”或“大数整除判断”的题目上卡壳查阅题解时满屏的≡符号和“模逆元”、“费马小定理”这些词才意识到自己错过了核心武器。同余理论将整数的研究从“绝对大小”的束缚中解放出来转而关注它们除以某个固定数模数后的“剩余类”。这种视角的转换在算法竞赛中威力巨大因为它能将无限范围的整数问题转化为在一个有限集合0到 m-1上的问题从而应用离散数学、群论等工具高效解决。简单来说当我们说a ≡ b (mod m)意思是a和b除以m的余数相同。这看似简单的定义却延伸出了模运算的完整体系模意义下的加减乘、指数运算、方程求解乃至更高级的原根、离散对数、中国剩余定理。这不仅是解决“答案对某数取模”类题目的基础更是理解许多经典算法如RSA加密、哈希函数、伪随机数生成内核的钥匙。本章我们就来系统性地拆解同余理论并聚焦于它在算法竞赛中的核心应用与实战坑点。2. 同余的定义、性质与基本运算规则2.1 严格定义与三种等价视角在数学上对于整数a, b和正整数ma ≡ b (mod m)当且仅当m整除(a - b)即m | (a - b)。这是最本质的定义。从编程和竞赛角度我们可以从三个等价且实用的视角来理解它余数相等视角a % m b % m。这是最直观的也是我们写判断语句时直接用的。差值整除视角(a - b) % m 0。这个视角在公式变形和证明中非常有用。“同余类”视角a和b属于模m的同一个剩余类。所有模m同余的整数构成一个集合称为一个同余类或剩余类。模m一共有m个不同的同余类[0], [1], ..., [m-1]。这个视角是理解模运算体系结构它构成一个环的基础。注意在竞赛和编程中我们通常约定a % m的结果在[0, m-1]范围内C/C、Java、Python等语言对负数取模行为不同需特别注意。这保证了每个整数都唯一地属于一个同余类。2.2 同余的基本性质算法推导的基石同余关系具有以下基本性质它们是我们进行模运算推导的“公理”自反性a ≡ a (mod m)对称性若a ≡ b (mod m)则b ≡ a (mod m)传递性若a ≡ b (mod m)且b ≡ c (mod m)则a ≡ c (mod m)加减乘运算保持性若a ≡ b (mod m),c ≡ d (mod m)则a ± c ≡ b ± d (mod m)若a ≡ b (mod m),c ≡ d (mod m)则a * c ≡ b * d (mod m)特别地a ≡ b (mod m)意味着a * k ≡ b * k (mod m)对任意整数k成立。这些性质保证了我们在模m意义下进行多项式运算时可以像普通整数一样处理加减乘最后再取模结果是一致的。这也是为什么我们可以在计算过程中不断取模以防止溢出的理论依据。但是除法或者说“除以一个数”在模运算中并不总是可行的这是同余运算与普通整数运算第一个关键区别也是竞赛中常见的坑点。2.3 模运算的“陷阱”与安全操作指南在普通算术中如果ac ≡ bc (mod m)我们可以两边同时除以c得到a ≡ b (mod m)。但在模运算中这需要附加条件。核心定理消去律如果ac ≡ bc (mod m)且gcd(c, m) 1即c与模数m互质那么可以推出a ≡ b (mod m)。如果gcd(c, m) d 1那么只能推出a ≡ b (mod m/d)。例如8 ≡ 20 (mod 12)即2*4 ≡ 5*4 (mod 12)。这里c4,m12,gcd(4,12)4。我们不能直接得到2 ≡ 5 (mod 12)但可以得到2 ≡ 5 (mod 3)因为12/43。实战中的安全操作守则加法/减法/乘法随时取模无脑安全。计算(a b) % m时最好写成(a % m b % m) % m以防止中间结果溢出即使a, b在long long范围内ab也可能溢出。除法/分数取模绝对禁止直接使用除法运算符/然后取模。必须转化为乘以“模逆元”下一节详解。这是新手最容易犯的错误会导致结果完全错误。负数取模确保结果非负。C/C中-5 % 3结果是-2而我们需要的是1。安全的处理方式是((a % m) m) % m。大数乘法取模即使是两个long long范围内的数相乘结果也可能超出long long范围约1e19。需要使用快速乘算法或直接使用__int128如果编译器支持。// 安全的模加法、减法和乘法模板 const int MOD 1e9 7; int add(int a, int b) { return (a b) % MOD; } int sub(int a, int b) { return ((a - b) % MOD MOD) % MOD; } int mul(int a, int b) { return (1LL * a * b) % MOD; } // 1LL 防止溢出 // 处理负数取模 int safe_mod(long long a, int m) { return (a % m m) % m; } // 防止大数乘法溢出的快速乘龟速乘 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; }3. 模逆元开启模意义下除法的钥匙既然不能直接除我们如何计算(a / b) % m呢答案就是寻找b在模m意义下的“逆元”。3.1 逆元的定义与存在条件整数a在模m意义下的逆元x定义为满足a * x ≡ 1 (mod m)的整数。可以把它理解为模意义下的“倒数”记作a^{-1}。逆元存在的充要条件是gcd(a, m) 1即a与模数m互质。这是一个至关重要的前提。在竞赛中常见的模数1e97、998244353都是质数因此所有不被该质数整除的数即1到m-1都存在逆元。一旦求得b的逆元inv_b那么(a / b) % m就可以转化为(a * inv_b) % m。3.2 求解逆元的三大实战算法3.2.1 费马小定理适用于模数为质数费马小定理若p是质数且gcd(a, p) 1则a^{p-1} ≡ 1 (mod p)。由此可得a * a^{p-2} ≡ 1 (mod p)因此a的逆元inv_a ≡ a^{p-2} (mod p)。这给出了一个用快速幂求逆元的简洁方法时间复杂度O(log p)。// 快速幂求逆元 (MOD 必须是质数且 a 与 MOD 互质) long long fast_pow(long long a, long long b, long long mod) { long long res 1; a % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } long long inv_fermat(long long a, long long mod) { return fast_pow(a, mod - 2, mod); }踩坑点务必先判断a % mod ! 0。如果a是mod的倍数则逆元不存在此时不能调用此函数。3.2.2 扩展欧几里得算法通用方法扩展欧几里得算法exgcd可以求解方程a*x b*y gcd(a, b)的整数解(x, y)。当gcd(a, m) 1时方程a*x m*y 1存在解。对等式两边取模m得到a*x ≡ 1 (mod m)此时的x就是a模m的逆元可能需要调整到[0, m-1]范围内。此方法不要求m是质数只要求a与m互质。// 扩展欧几里得算法求逆元 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 d exgcd(b, a % b, y, x); y - (a / b) * x; return d; } long long inv_exgcd(long long a, long long mod) { long long x, y; long long d exgcd(a, mod, x, y); if (d ! 1) return -1; // 逆元不存在 return (x % mod mod) % mod; // 调整到正数范围 }3.2.3 线性递推求逆元批量求解当需要求1到n所有数模质数p的逆元时使用线性递推法是O(n)的效率极高。递推公式inv[1] 1inv[i] (p - p / i) * inv[p % i] % pi 1这个公式的推导基于p % i和i的关系利用已经求得的更小数的逆元来递推。// 线性递推求 1~n 的逆元 (MOD 必须是质数) const int MAXN 1e6 5; const long long MOD 1e9 7; long long inv[MAXN]; void init_inv(int n) { inv[1] 1; for (int i 2; i n; i) { inv[i] (MOD - MOD / i) * inv[MOD % i] % MOD; } }算法选择策略单次求逆模数为质数时用快速幂代码最短最清晰。模数非质数但互质用扩展欧几里得。需要预处理大量逆元如组合数计算用线性递推。4. 同余方程从简单线性到中国剩余定理4.1 线性同余方程ax ≡ b (mod m)这是最基本的形式。方程有解的充要条件是gcd(a, m) | b。求解步骤设d gcd(a, m)。如果d不能整除b则无解。方程两边同除以d得到(a/d)x ≡ (b/d) (mod m/d)。此时a/d与m/d互质。求a/d在模m/d意义下的逆元inv。则特解x0 (b/d) * inv % (m/d)。方程的通解为x ≡ x0 k * (m/d) (mod m)k 0, 1, ..., d-1。即在模m意义下有d个解。// 求解线性同余方程 ax ≡ b (mod m)返回所有解模 m 意义下 vectorlong long linear_congruence(long long a, long long b, long long m) { vectorlong long solutions; long long x, y; long long d exgcd(a, m, x, y); // 使用之前的 exgcd 函数 if (b % d ! 0) return solutions; // 无解 long long t m / d; long long x0 (x * (b / d) % t t) % t; // 最小非负特解模 m/d for (int i 0; i d; i) { solutions.push_back((x0 i * t) % m); } return solutions; }4.2 中国剩余定理解同余方程组的利器中国剩余定理解决的是形式为x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ an (mod mn)的一次同余方程组其中m1, m2, ..., mn两两互质。CRT给出了一个构造解的通法并且解在模M m1*m2*...*mn意义下是唯一的。构造解的过程Garner算法思想计算总模数M ∏ mi。对于第i个方程计算Mi M / mi。计算Mi在模mi意义下的逆元ti即Mi * ti ≡ 1 (mod mi)。则方程组的解为x ≡ Σ(ai * Mi * ti) (mod M)。// 中国剩余定理 (CRT)模数两两互质 long long crt(const vectorlong long a, const vectorlong long m) { long long M 1, x 0; int n a.size(); for (int i 0; i n; i) M * m[i]; for (int i 0; i n; i) { long long Mi M / m[i]; long long ti inv_exgcd(Mi, m[i]); // 求逆元 x (x a[i] * Mi % M * ti % M) % M; } return (x M) % M; }实战中的关键点与扩展模数不互质怎么办此时需要使用扩展中国剩余定理。其核心思想是将两个方程不断合并。对于方程x ≡ a1 (mod m1)和x ≡ a2 (mod m2)等价于寻找x a1 k1*m1 a2 k2*m2即k1*m1 - k2*m2 a2 - a1。这是一个线性丢番图方程可用exgcd求解k1从而得到合并后的新方程x ≡ a1 k1*m1 (mod lcm(m1, m2))。重复此过程直到合并所有方程。解的唯一性CRT保证在模M意义下有唯一解。这意味着所有解的形式是x k*M。应用场景CRT不仅用于直接解方程组更常用于“拆模数”优化。例如需要用FFT计算大数乘法但结果可能超过double精度或long long范围时可以选取多个质数作为模数分别计算最后用CRT将结果合并回原模数或更大的数下的值。5. 欧拉定理、费马小定理与指数循环节5.1 欧拉定理更一般的费马小定理欧拉定理若gcd(a, m) 1则a^{φ(m)} ≡ 1 (mod m)。其中φ(m)是欧拉函数表示1到m中与m互质的数的个数。当m是质数p时φ(p) p-1欧拉定理退化为费马小定理。欧拉定理的竞赛应用求模意义下的幂的逆元a^{φ(m)-1}是a模m的逆元当gcd(a,m)1。简化大指数幂运算计算a^b mod m当gcd(a, m)1时可以利用a^b ≡ a^{b mod φ(m)} (mod m)来降低指数大小。这是解决“求a^b^c^... mod m”这类套娃指数题的关键。5.2 指数循环节扩展欧拉定理当gcd(a, m) ≠ 1时欧拉定理不成立。但有一个更强的结论常被称为扩展欧拉定理或指数循环节对于a^b mod m有如果b φ(m)直接计算a^b mod m。如果b ≥ φ(m)则a^b ≡ a^{b mod φ(m) φ(m)} (mod m)。这个公式没有互质条件是解决一大类幂模问题的终极武器。其证明较复杂但应用起来非常直接。经典例题模式计算a^b^c^... mod m其中指数是塔状结构。解题步骤递归地应用扩展欧拉定理从最顶层的指数开始。在递归过程中需要计算欧拉函数φ。注意当m降到1时任何数模1都是0可以作为递归终点。判断指数b是否≥ φ(m)是关键这通常需要小心处理因为b本身可能极大。一个实用技巧是在递归计算指数时如果发现当前结果已经≥ φ(m)就记录一个标志位并在最终计算幂时加上φ(m)。// 递归计算 a^b mod m其中 b 是以字符串或大数形式给出的极大指数 // 这里假设有一个函数 get_phi(m) 计算欧拉函数 long long solve(long long a, string b_str, long long m) { if (m 1) return 0; long long phi_m get_phi(m); long long b_mod 0; bool flag false; // 标记 b phi_m // 将字符串 b_str 转化为模 phi_m 的值并判断是否 phi_m for (char ch : b_str) { b_mod b_mod * 10 (ch - 0); if (b_mod phi_m) { flag true; b_mod % phi_m; } } if (flag) { b_mod phi_m; // 应用扩展欧拉定理 } return fast_pow(a, b_mod, m); } // 对于 a^b^c mod m需要递归调用 solve(a, b_str, m)其中 b_str 是 c 的字符串但计算 b^c 时又需要模 phi(m)...踩坑实录我曾在一道题上WA了无数次就是因为忽略了b φ(m)的情况直接套用了加φ(m)的公式。当b很大但以字符串给出时判断b是否≥ φ(m)需要边转换边判断不能先全部转换成数字可能溢出也不能先取模会丢失大小信息。必须采用上述代码中的方法在逐位转换的过程中同步判断和取模。6. 同余理论在竞赛中的经典应用场景6.1 大数取模与读入优化题目常常给出一个长达10^5位的大整数N要求计算N % M。直接使用高精度库可能超时或超内存。技巧利用同余的加法、乘法性质边读入边取模。string s; // 大整数的字符串表示 long long m; long long mod 0; for (char ch : s) { mod (mod * 10 (ch - 0)) % m; } // 循环结束后mod 就是 N % m 的结果原理就是(a*10 b) % m ((a%m)*10 b) % m。6.2 分数取模与组合数计算竞赛中大量问题涉及组合数C(n, k) % MOD。计算公式为n! / (k! * (n-k)!)。这需要用到除法取模即逆元。预处理阶乘和阶乘逆元是标准操作const int MAXN 1e6 5; const long long MOD 1e9 7; long long fac[MAXN], inv_fac[MAXN]; void init_comb() { fac[0] 1; for (int i 1; i MAXN; i) fac[i] fac[i-1] * i % MOD; // 预处理阶乘逆元 inv_fac[i] (i!)^{-1} mod MOD // 方法一费马小定理 inv_fac[MAXN-1] fast_pow(fac[MAXN-1], MOD-2); // 然后逆推 inv_fac[i] inv_fac[i1] * (i1) % MOD // 方法二线性求逆元后相乘 inv_fac[0] 1; for (int i 1; i MAXN; i) inv_fac[i] inv_fac[i-1] * inv[i] % MOD; // inv[i] 是 i 的逆元 } long long C(int n, int k) { if (k 0 || k n) return 0; return fac[n] * inv_fac[k] % MOD * inv_fac[n-k] % MOD; }6.3 哈希与字符串匹配字符串哈希的核心思想是将字符串映射为一个整数哈希值并利用同余性质通常选择一个大质数作为模数来快速计算子串哈希从而进行字符串比较。滚动哈希Rabin-Karp算法 给定字符串s定义哈希函数H(s) (s[0]*B^{n-1} s[1]*B^{n-2} ... s[n-1]) % M其中B是基数如131, 13331M是大质数。 则子串s[l..r]的哈希值为H(s[l..r]) (H(r) - H(l-1) * B^{r-l1} % M M) % M其中H(i)是前缀s[0..i]的哈希值。这里就运用了同余的减法性质。双哈希防冲突单哈希可能发生冲突不同字符串哈希值相同。常用策略是选择两套不同的(B, M)计算两个哈希值只有当两个哈希值都相等时才认为字符串相等冲突概率极低。6.4 寻找循环节与模线性递推许多问题最终会归结为求f(n) % m其中f(n)是一个递推数列如斐波那契数列。由于模m运算数列f(n) mod m的值域是有限的0到m-1因此必然会出现循环即存在p皮萨诺周期使得f(np) ≡ f(n) (mod m)。寻找循环节的方法暴力找循环节起点和周期记录(f(i), f(i1))这个状态对因为递推通常只依赖前两项。当某个状态对重复出现时就找到了循环节。复杂度O(m^2)理论上界但实际周期通常远小于m^2。利用数学性质对于斐波那契数列模m其周期与m的质因数分解有关最大不超过6m。找到循环节p后求f(n) mod m就转化为求f(n % p) mod m可以将n从极大的范围如1e18降到p以内计算。6.5 离散对数问题与BSGS算法离散对数问题是给定a, b, m通常gcd(a, m)1求最小的非负整数x使得a^x ≡ b (mod m)。记作x ind_a b。大步小步算法是解决离散对数的经典算法时间复杂度O(√m log m)。算法思想设x i * t - j其中t ceil(√m)0 j t。则方程变为a^{i*t} ≡ b * a^j (mod m)。预处理“小步”计算所有b * a^j mod mj0..t-1存入哈希表或map。枚举“大步”计算(a^t)^i mod mi1..t并在哈希表中查找。若找到相等的值则x i*t - j就是一个解取最小的非负解。// 大步小步算法 (Baby-Step Giant-Step) long long bsgs(long long a, long long b, long long m) { a % m; b % m; if (b 1 || m 1) return 0; // 特殊情况 unordered_maplong long, long long hash; long long t (long long)sqrt(m) 1; long long val b; for (long long j 0; j t; j) { hash[val] j; val val * a % m; } a fast_pow(a, t, m); // a^t val 1; for (long long i 1; i t; i) { val val * a % m; if (hash.count(val)) { long long ans i * t - hash[val]; if (ans 0) return ans; } } return -1; // 无解 }BSGS算法在密码学如Diffie-Hellman密钥交换和某些数论竞赛题中很有用。需要注意a和m互质的前提若不互质则需要使用扩展BSGS算法。同余理论是算法竞赛数论板块的脊柱它将散落的知识点串联成一个强有力的工具集。从最基本的取模运算到逆元、CRT、欧拉定理再到应用层的哈希、循环节、离散对数理解并熟练运用这一体系能让你在面对绝大多数数论题目时都能找到清晰的思考路径。我个人的体会是初期一定要亲手推导每一个定理和公式并完成足够多的练习题来建立直觉。例如遇到分数就想逆元遇到大指数就想欧拉定理降幂遇到方程组就想CRT。当这些思维成为条件反射时数论就从拦路虎变成了你的得分利器。最后一个小建议自己整理一份模版代码包含安全的加减乘取模函数、快速幂、exgcd求逆元、线性递推逆元、CRT、欧拉函数、BSGS等并反复测试其正确性这能在比赛中为你节省大量时间并避免低级错误。