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=3 | result=3;base²=9,exp=6 | 取最低位 1 |
| exp=6 | result=3;base²=13,exp=3 | 最低位 0 跳过 |
| exp=3 | result=3×13 mod17=5;base²=16,exp=1 | 再次取位 |
| exp=1 | result=5×16 mod17=12 | 最终答案 |
窄屏可左右滑动表格,阅读完整计算与理由。
只处理指数的四个二进制位。
04为什么这个方法成立
- 初始 result=1,base=a,恒等式成立。
- 奇偶两种更新都保持 result·base^exp 不变。
- 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
7^0 mod13 是多少?
需要一点提示
空乘积。
查看解析与答案
1。
为什么中途取模不改变最终余数?
需要一点提示
乘法保持同余。
查看解析与答案
若 x≡x'、y≡y',则 xy≡x'y',可逐步替换中间值。
负指数如何处理?
需要一点提示
先求底数逆元。
查看解析与答案
当 gcd(base,mod)=1 时,用逆元的正指数幂;不可逆时该模下负幂一般无定义。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂