1. 从一道题说起当模运算遇上除法最近在刷算法题特别是数论相关的总会遇到一个绕不开的坎模运算下的除法。比如题目要求计算(a / b) % p的值其中p是一个质数。如果你直接按照(a % p) / (b % p)来计算大概率会得到一个错误的结果甚至程序会直接报错因为整数除法在模运算下没有定义。这就像在一个只有加法和乘法的世界里突然有人问你“一半”是多少你没法直接用现有的规则回答。这个“除法”问题在数论中有一个优雅的解决方案乘法逆元。简单来说在模p的世界里我们不能直接做除法a / b但我们可以寻找一个数x使得b * x ≡ 1 (mod p)成立。这个x就是b在模p意义下的乘法逆元记作b^{-1}。找到了它原来的(a / b) % p就可以转化为(a * b^{-1}) % p完美地规避了除法全部用乘法和取模就能解决。那么核心问题就变成了如何高效地求出这个逆元b^{-1}这就是AcWing 876. 快速幂求逆元这道题要教会我们的核心技能。它不仅是数论的基础更是解决许多组合数学、密码学问题的关键钥匙。今天我们就来彻底拆解它从为什么需要逆元到如何用快速幂求解再到实际编码中的各种坑手把手带你掌握这个必会知识点。2. 逆元究竟是什么为什么模运算下除法这么难要理解逆元我们必须先回到模运算的基本性质。我们常说的取模运算构建了一个叫做“模p剩余系”的数学系统。在这个系统里我们只关心0到p-1这p个数任何运算结果超出这个范围我们都会通过取模把它“拉”回来。在这个系统里加法和乘法是封闭且友好的(a b) % p ((a % p) (b % p)) % p(a * b) % p ((a % p) * (b % p)) % p但是除法(a / b) % p却不行。原因在于除法的本质是乘法的逆运算。在实数里a / b等价于a * (1/b)而1/b是b的乘法逆元满足b * (1/b) 1。在模p的世界里我们也想找一个类似的“1/b”即一个数x使得b * x ≡ 1 (mod p)。这个x就是b模p的逆元。这里有一个至关重要的前提b和模数p必须互质最大公约数为1。如果b和p不互质那么逆元不存在。想象一下如果b和p有公因数d那么b * x永远会是d的倍数它模p的结果也永远是d的倍数不可能等于1因为1不是d的倍数除非d1。在 AcWing 876 这道题以及绝大多数算法竞赛场景中模数p被指定为一个质数。这是一个非常巧妙且强大的设定。因为p是质数那么对于任何不是p的倍数的整数b即b % p ! 0b和p一定是互质的质数的因数只有1和它自身。这就保证了在p是质数且b不是p的倍数时b的逆元一定存在且唯一。所以逆元就是在模运算中扮演“倒数”角色的那个数。找到了它我们就能把棘手的模除法转化为熟悉的模乘法。3. 费马小定理连接质数、幂运算与逆元的桥梁既然知道了逆元需要满足b * x ≡ 1 (mod p)我们该如何求解x呢这里就需要请出数论中的一个著名定理——费马小定理。费马小定理是这样描述的如果p是一个质数且整数a不是p的倍数即p不整除a那么有a^{p-1} ≡ 1 (mod p)这个定理非常强大。我们把它稍微变形一下a * a^{p-2} ≡ 1 (mod p)现在请对比一下逆元的定义式b * x ≡ 1 (mod p)。你会发现如果我们令a b那么x a^{p-2} (mod p)恰好就满足了逆元的条件因此我们得到了一个在模数p为质数时计算b的逆元的公式b^{-1} ≡ b^{p-2} (mod p)问题瞬间转化了求逆元变成了求b的(p-2)次幂再对p取模。这依然是一个巨大的计算量如果p很大比如10^97直接计算b^(p-2)是天文数字完全不现实。这时候就需要我们的下一个利器登场了。4. 快速幂算法如何光速计算大整数的高次幂快速幂算法的核心思想是二分和位运算它能把一个线性时间的幂运算O(n)优化到对数时间O(log n)。这对于计算b^(p-2)这种指数巨大的运算是救星。它的原理基于一个简单的等式a^n (a^{n/2})^2当n为偶数时。我们通过不断将指数折半将乘法次数从n次降低到大约log2(n)次。具体实现时我们通常采用基于二进制拆分的迭代方法这样更高效且不易栈溢出。思路如下初始化结果res 1。将指数n看作一个二进制数。只要n 0就循环 a. 如果n的二进制最低位是1即n 1为真说明当前位有权重需要将当前的底数a乘到结果res中并对p取模。 b. 无论最低位是否为1都需要将底数a自我平方一次即a a * a % p为处理下一位二进制位做准备。 c. 将指数n右移一位即n 1相当于除以2向下取整。循环结束后res即为a^n % p的结果。为什么每一步都要取模这是为了防止数值溢出。在计算过程中即便是中间结果也可能非常大及时取模可以保证所有运算都在可控的范围内进行。我们来看一个具体的例子计算3^13 % 7n13 (二进制1101) a3 res1第一轮n11res 1*3 %7 3a 3*3%72n6第二轮n10res不变为3a 2*2%74n3第三轮n11res 3*4%75a 4*4%72n1第四轮n11res 5*2%73a 2*2%74n0最终结果res 3。可以验证3^1315943231594323 % 7 3。快速幂的模板代码非常简洁是必须背下来的算法核心之一。// 计算 a^k % p long long qmi(long long a, long long k, long long p) { long long res 1; while (k) { if (k 1) res res * a % p; a a * a % p; k 1; } return res; }5. 代码实现与逐行解析把公式变成程序结合费马小定理和快速幂求逆元的代码就呼之欲出了。根据公式inv(b) b^{p-2} % p我们只需要调用快速幂函数qmi(b, p-2, p)即可。但题目不会这么简单。AcWing 876 通常是多组查询并且需要处理逆元不存在的情况。下面是一个完整的、带有详细注释的C实现。#include iostream using namespace std; // 快速幂模板函数 // a: 底数k: 指数p: 模数 long long qmi(long long a, long long k, long long p) { long long res 1; // 当指数k还未被分解完时继续循环 while (k) { // 如果当前k的二进制最低位是1则将当前的a乘入结果 if (k 1) res res * a % p; // 底数自我平方为处理下一位做准备 a a * a % p; // 指数右移一位相当于除以2 k 1; } return res; } int main() { int n; cin n; // 读取查询次数 while (n--) { long long a, p; cin a p; // 读取要求逆元的数a和模数p // 关键判断逆元存在的条件 // 已知p是质数根据费马小定理a必须不是p的倍数。 // 即 a % p ! 0。但更直接的判断是a和p互质。 // 由于p是质数只要a不是p的倍数它们就互质。 // 当a是p的倍数时a%p0此时逆元不存在。 if (a % p 0) { // a是p的倍数不互质逆元不存在 cout impossible endl; } else { // 逆元存在根据费马小定理inv(a) a^(p-2) % p cout qmi(a, p - 2, p) endl; } } return 0; }逐行解析与思考函数qmi这是算法的发动机。注意所有变量和返回值都使用long long这是因为中间结果a * a很可能超出int范围即使最终会取模。使用long long是防止溢出的安全做法。主函数中的判断if (a % p 0)这是整个程序的安全阀也是最容易忽略的边界条件。很多人记住了公式却忘了前提。当a是p的倍数时a和质数p不互质最大公约数是p费马小定理不适用逆元不存在。必须特判输出impossible。计算qmi(a, p-2, p)直接套用公式。这里指数是p-2为什么不是p-1因为我们要的是a * a^{p-2} ≡ 1所以逆元是a^{p-2}而不是a^{p-1}a^{p-1} ≡ 1它是1不是逆元。多组输入这是一个经典框架用于处理多个独立的求逆元请求。注意这里有一个非常重要的细节。判断条件是a % p 0。在数学上当a和p不互质时逆元不存在。由于p是质数a和p不互质等价于a是p的倍数即a % p 0。但如果题目没有明确说明p是质数这个判断就不正确了需要改用欧几里得算法判断gcd(a, p) 1。本题环境已规定p为质数故用取模判断更直接高效。6. 边界情况、易错点与实战心得即使理解了原理和代码在实际解题和竞赛中依然会踩到一些坑。下面是我在多次实践中总结出的关键点。6.1 数据类型与溢出看不见的“炸弹”这是最隐蔽的错误。看看这行代码a a * a % p。如果a是int类型假设a1e9p1e97那么a*a的结果大约是1e18这已经远远超过了int的最大值约2.1e9会发生溢出导致计算错误即使后面取了模也为时已晚。解决方案在模运算和幂运算中无脑使用long long是一种好习惯。更保守的做法是在乘法时使用强制类型转换或者直接使用C 11的int64_t。我们的模板中全部使用long long就是为了从根本上避免这个问题。6.2 对“逆元不存在”条件的深刻理解很多初学者会忘记判断逆元是否存在。我们必须时刻牢记逆元存在的前提是a与p互质。在本题p为质数中条件简化为a不是p的倍数 (a % p ! 0)。如果p不是质数你必须使用欧几里得算法计算gcd(a, p)只有当最大公约数为1时逆元才存在。此时需要用扩展欧几里得算法来求逆元费马小定理不再适用。一个常见的思维陷阱当a0时怎么办0和任何数p的最大公约数都是p因为gcd(0, p) p。所以0在模p意义下永远没有逆元这也符合直觉因为你不能定义一个数x使得0 * x ≡ 1 (mod p)。在我们的代码中0 % p 0成立所以会被正确判断为impossible。6.3 快速幂的递归与迭代选择与风险快速幂有递归和迭代两种写法。递归写法pow(a, n) (n%20) ? pow(a*a, n/2) : a*pow(a*a, n/2)虽然直观但当指数n很大比如1e9时递归深度会非常深有栈溢出的风险。因此在算法竞赛和工程中迭代写法是绝对的首选。它效率高且没有栈溢出风险。6.4 模运算的优先级括号是你的朋友在C中取模运算符%的优先级与乘除法相同。但为了代码绝对清晰避免因优先级理解错误导致的bug建议在涉及多个运算时主动使用括号。 例如res res * a % p是安全的因为*和%优先级相同从左向右结合。但如果你写成res a * b % p * c % p虽然结合顺序是(((a*b)%p)*c)%p符合预期但可读性差。更清晰的写法是res (((a * b) % p) * c) % p。在初学阶段多用括号有益无害。7. 逆元的其他求法扩展欧几里得算法费马小定理快速幂是求逆元在模数为质数时的“特快专列”。但它的应用有局限性必须要求模数p是质数。如果p不是质数但a和p互质我们该如何求逆元呢这时就需要更通用的工具——扩展欧几里得算法。扩展欧几里得算法可以在求出a和p的最大公约数gcd(a, p)的同时找到一组整数x, y满足贝祖等式a*x p*y gcd(a, p)。当a和p互质时gcd(a, p) 1。贝祖等式就变成了a*x p*y 1。 我们对这个等式两边同时模p得到a*x ≡ 1 (mod p)。 看这里的x就是a模p的逆元而且这个方法不要求p是质数只要求a和p互质。扩展欧几里得算法的C实现如下// 扩展欧几里得算法返回gcd(a,b)并通过引用返回x,y 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); // 注意这里交换了x,y y - a / b * x; return d; } // 使用扩展欧几里得求逆元 int inv(int a, int p) { int x, y; int d exgcd(a, p, x, y); if (d ! 1) return -1; // 逆元不存在 // 保证逆元是正数 return (x % p p) % p; }对比与选择费马小定理快速幂时间复杂度O(log p)。仅当p为质数时可用。代码极简效率高。扩展欧几里得算法时间复杂度O(log min(a, p))。只要a与p互质即可用通用性更强。代码稍复杂。在算法竞赛中如果题目明确说明模数p是质数尤其是像1e97998244353这样的常用质数优先使用快速幂法因为它写起来快不易错。如果模数性质未知或者需要判断逆元是否存在通过检查gcd是否为1则必须使用扩展欧几里得算法。8. 逆元的典型应用场景不止于一道题掌握了求逆元的方法它究竟能用来做什么这绝不仅仅是为了解一道题。1. 组合数计算模意义下计算组合数C(n, m) n! / (m! * (n-m)!)是算法竞赛中的高频操作。直接计算阶乘再相除中间结果会巨大无比。通常我们会预处理出阶乘数组fact[i] i! % p和阶乘逆元数组infact[i] (i!)^{-1} % p。那么组合数就可以通过乘法快速计算C(n, m) % p fact[n] * infact[m] % p * infact[n-m] % p这里infact[i]就是fact[i]的逆元可以用快速幂预先求出。2. 分数取模任何形如(a / b) % p的计算在b和p互质的前提下都可以转化为(a * inv(b)) % p。这在处理概率、有理数运算的题目中非常常见。3. 线性同余方程求解对于方程a*x ≡ b (mod p)如果a和p互质可以在两边同时乘以a的逆元得到x ≡ b * inv(a) (mod p)。4. 模数为质数时的除法运算替换在动态规划等场景中如果状态转移涉及除法且模数是质数就可以用乘逆元来代替保证所有运算都在模意义下进行。可以说逆元是打开模运算世界大门的一把关键钥匙是将数论知识应用于实际算法问题的桥梁。理解并熟练运用它是迈向更高阶算法学习的必经之路。回过头看 AcWing 876 这道题它看似简单只是一个模板函数调用。但它背后串联起了模运算的本质、费马小定理的应用、快速幂的优化思想以及边界条件的处理。把这些都搞明白了下次遇到任何需要模逆元的地方你都能从容应对。编程实现时牢记用long long、记得特判、理解算法每一步的意义这才是从“看懂”到“掌握”的关键。