模运算与快速幂

数学、数论与组合 · HTML

数学 / 逻辑形态

若 a≡b(mod M)，加乘保持同余；快速幂按指数二进制位累乘 base^(2^k)。

识别信号

• 答案要求对 M 取模
• 指数极大
• 需模逆元或组合数
• 中间乘积可能爆炸
• 状态只需保留余数

容易误判的相似信号

核心不变量

快速幂中 result*base^exp 与原目标同余；每步处理一位并令 base 平方、exp 折半。

状态、转移与处理顺序

Python 骨架

def mod_pow(base, exp, mod):
    if mod <= 0 or exp < 0:
        raise ValueError
    result = 1 % mod
    base %= mod
    while exp:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

def prime_mod_inverse(a, p):
    if a % p == 0: raise ZeroDivisionError
    return mod_pow(a, p-2, p)

正确性思路

1. 指数二进制分解为若干 2^k 之和。
2. 最低位为 1 时当前 base 正是相应 2^k 次幂。
3. 平方与右移保持 result*base^exp 的同余不变量。
4. exp 归零时 result 等于目标幂的模。

复杂度

边界条件

• exp=0 返回 1 mod M
• mod=1 时结果为 0
• 负 base 先规范化
• 逆元要求 gcd(a,M)=1
• 固定宽度语言乘法可能先溢出

错误模式

选择与排除规则

• 巨大指数：binary exponentiation。
• 加乘计数：每个转移及时取模。
• 模数为质数且分母非零：可用费马逆元。
• 合数模数：用扩展欧几里得检验互质。

相关模板

原创微型例子

Recall prompts

• 快速幂循环不变量是什么？
• 何时模逆元不存在？
• 为何取模不能保留大小关系？

我的补充