使用费马定理求模逆元
安全地在模数下进行除法
使用费马定理求模逆元 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
模运算下的除法会失效
加法、减法和乘法在模数下都能正常进行，但普通除法不行。您不能直接做除法再取余数。⚠️
用乘法替代除法
解决方法是使用模逆元：除以 x 就变成乘以 x 的逆元。因此，a / b mod m 可以转换为 a 乘以 b 的逆元。
什么是逆元
x 的逆元是这样一个数：它与 x 在模数下相乘后得到 1。它在模运算中扮演普通算术里 1/x 的角色。
# x * inv(x) % m == 1质数让它成为可能
只有当 x 与 m 没有公共因子时，逆元才存在。使用 1e9+7 这样的素数模数，就能保证每个非零 x 都有逆元。
费马小定理登场
费马小定理指出，对于质数 p，只要 x 不是 p 的倍数，x 的 p - 1 次方就与 1 同余。
# x^(p-1) % p == 1推导逆元
从等式中分离出一个 x 因子，剩下的部分就必须是它的逆元。因此，x 的逆元就是 x 的 p - 2 次方再对 p 取模。
# inv(x) = x^(p-2) % p用快速幂计算
这个指数很大，因此请使用上一节介绍的快速幂运算。在 Python 中，调用一次幂函数即可完成全部计算。
inv = pow(x, MOD - 2, MOD)用它完成除法
要在模数下计算 a 除以 b，就将 a 乘以 b 的逆元。所得余数正好是真实商对 p 取模的结果。
ans = a * pow(b, MOD - 2, MOD) % MOD永远不要对零求逆
0没有逆元，因为任何数乘以零都不可能得到 1。请防止除以在模数下约减为零的值。
求一个逆元的代价
每个费马逆元都需要进行一次快速幂，因此需要O(log p)的时间。少量除法的代价很低，但如果计算数百万次，成本就会累积起来。
批量求逆的提示
需要求许多逆元时，可以通过一次巧妙的线性遍历预先计算它们，而不是为每个元素调用一次幂函数。下一节计算 nCr 时会用到这种方法。
快速检查
在素数模数下，哪个幂可以得到模逆元？
回顾
现在您可以在素数模数下，通过乘以模逆元来完成除法。逆元可以通过 pow 计算为 x 的 p - 2 次方。只要记住，永远不要对零求逆。✅
常见问题解答
「使用费马定理求模逆元」课时是免费的吗？
是的 — 「使用费马定理求模逆元」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「使用费马定理求模逆元」这节课中我会学到什么？
安全地在模数下进行除法 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「使用费马定理求模逆元」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 在素数模数下运算
- 快速模幂运算
- 使用费马定理求模逆元
- 使用预计算阶乘计算 nCr