快速模幂运算
使用 pow(a, b, m) 计算幂
快速模幂运算 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
幂运算问题
您经常需要在模数下计算一个数的超大次幂。如果一次只乘一个因子，就需要太多步骤。⚡
朴素方法太慢
一个重复乘 b 次的循环需要O(b)步。当指数接近十亿时，程序还没完成就会超出时间限制。
for _ in range(b): r = r * a % MOD通过平方更快地提升幂次
诀窍在于平方：a 的 8 次方等于 ((a 的平方) 的平方) 的平方。每次平方都会让指数翻倍，因此只需很少几步就能得到很大的幂。
用二进制读取指数
每个指数都可以表示为若干个 2 的幂之和，也就是它的二进制形式。因此，只需乘入那些对应位为 1 的底数幂，跳过其余部分。
# 13 = 1101 -> a^8 * a^4 * a^1检查最低位
查看b & 1即可检查最低位。如果结果为 1，就在继续之前将当前底数合并到当前结果中。
if b & 1: result = result * base % MOD每轮都移位并平方
检查每一位后，将底数平方，并将指数向右移动一位。对于任何现实规模的输入，循环通常只运行约 30 到 60 次。
base = base * base % MOD
b >>= 1组合起来
将 result 初始化为 1，然后在指数为正时循环执行。这个完整的快速幂运算思想也称为二进制幂或平方求幂。
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1复杂度是对数级
由于每一轮都会将指数减半，所需时间为O(log b)。这样，十亿次乘法就变成大约三十次，完全能够满足时间限制。
Python 提供了 pow
您很少需要亲自编写这个循环：Python 内置的pow(a, b, m)会以接近 C 的速度为您完成快速模幂运算。
print(pow(2, 100, MOD))它很快就会派上用场
快速幂是通过费马定理求模逆元的基础，下一节就会介绍它。现在掌握快速幂，模运算下的除法就会变得简单。
先处理底数
在循环之前，先用base % MOD约减底数。如果底数已经大于模数，否则每次平方都会产生更大的数。
base = a % MOD快速检查
快速模幂运算的速度有多快？
回顾
现在您可以通过平方和读取二进制位，在O(log b)时间内计算超大指数的幂。在 Python 中，只需调用 pow(a, b, m) 即可。🚀
常见问题解答
「快速模幂运算」课时是免费的吗？
是的 — 「快速模幂运算」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「快速模幂运算」这节课中我会学到什么？
使用 pow(a, b, m) 计算幂 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「快速模幂运算」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。