专题进阶 · 数学算法推荐总顺序 · 第 96 / 148 课

按指数二进制拆解,利用循环不变量证明反复平方。

先学会这些,再进入本课 模运算
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数学算法

快速幂Binary Exponentiation

按指数二进制拆解,反复平方,在 O(log k) 次乘法内计算 aᵏ。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

按指数二进制拆解,利用循环不变量证明反复平方。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

求 3^13 mod 17,逐乘要 13 次,能否把指数每轮减半?

02一步步得到方法

把指数写成二进制

13=8+4+1,因此 3^13=3^8·3^4·3。连续平方得到 3、3²、3⁴、3⁸,只把对应指数位为 1 的因子乘入答案。

循环中 base 表示当前二进制位对应的幂,exp 的最低位决定是否使用它;然后 base 平方、exp 整除 2。模运算与乘法兼容,所以每步可取模。

不变量比记位运算更可靠

设原问题为 a^n,循环始终保持 result·base^exp≡a^n。若 exp 为奇数,先把一个 base 乘入 result,再把剩下的偶数指数折半;若为偶数直接平方折半。

n=0 时返回乘法单位元 1(模 1 时为 0)。负指数需要可逆性与另外的接口,本课仅处理非负整数指数。

二进制位表示要乘哪些幂

把指数 e 写成二进制,a^e 就是若干 a^(2^k) 的乘积。循环中底数每次平方,恰好依次生成这些幂;当前指数最低位为1时,把对应幂乘进答案。

不变量可以写成 answer×base^remaining 等于原始目标值(模版本为同余)。处理一位后把剩余指数右移,直到0,答案保留全部需要的因子。

03把一个小例子完全算清楚

3^13 mod 17。

步骤计算与状态为什么这样做
exp=13,base=3result=3;base²=9,exp=6取最低位 1
exp=6result=3;base²=13,exp=3最低位 0 跳过
exp=3result=3×13 mod17=5;base²=16,exp=1再次取位
exp=1result=5×16 mod17=12最终答案

窄屏可左右滑动表格,阅读完整计算与理由。

只处理指数的四个二进制位。

04为什么这个方法成立

  1. 初始 result=1,base=a,恒等式成立。
  2. 奇偶两种更新都保持 result·base^exp 不变。
  3. exp 严格折半到 0,剩下 result 即原幂的模值。

05把推导翻译成代码

Python · 可独立运行的教学实现

def mod_power(base,exp,mod):
    assert exp >= 0 and mod > 0
    result = 1%mod
    base %= mod
    while exp:
        if exp & 1:
            result = result*base%mod
        base = base*base%mod
        exp //= 2
    return result

逐个理解关键决定

exp & 1
检查最低二进制位是否为 1。
base = base*base%mod
下一轮处理的幂次翻倍,不是 base 加倍。

06时间、空间与实现范围

O(log(exp+1)) 次乘法,常数个数值状态;实际大整数乘法成本与模数位数有关。

同一框架可用于矩阵等具有结合律和单位元的乘法,不要求运算可交换,但次序必须一致。

07改变条件,检查哪里会出错

将 base 平方写成乘 2

指数翻倍对应底数平方,不是数值翻倍。

把负指数直接送入整数右移循环

本课整数快速幂要求非负指数;负指数需倒数或模逆元,并检查是否存在。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

7^0 mod13 是多少?

需要一点提示

空乘积。

查看解析与答案

1。

练习 2 · 边界与辨析

为什么中途取模不改变最终余数?

需要一点提示

乘法保持同余。

查看解析与答案

若 x≡x'、y≡y',则 xy≡x'y',可逐步替换中间值。

练习 3 · 变式与迁移

负指数如何处理?

需要一点提示

先求底数逆元。

查看解析与答案

当 gcd(base,mod)=1 时,用逆元的正指数幂;不可逆时该模下负幂一般无定义。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。