快速幂

快速幂(参考OI Wiki)

背景

计算𝑎的𝑛次方表示将𝑛个𝑎乘在一起：$𝑎^𝑛 =𝑎×𝑎⋯×𝑎(𝑛 个a)$。然而当 𝑛 太大或单次乘法开销太大的时侯，这种方法就不太适用了

基本思想

将取幂的任务按照指数的 二进制表示 来分割成更小的任务。

具体实现

迭代版本

设 𝑛 的二进制表示为 $(𝑛_𝑡𝑛_{𝑡−1}⋯𝑛_1𝑛_0)_2$，也就是说，有

$$𝑛=𝑛_𝑡2^𝑡+𝑛_{𝑡−1}2^{𝑡−1}+⋯+𝑛_12^1+𝑛_02^0$$

其中，𝑛𝑖 ∈{0,1}。那么，就有

$$𝑎^𝑛=𝑎^{𝑛_𝑡2^𝑡+𝑛_{𝑡−1}2^{𝑡−1}+⋯+𝑛_12^1+𝑛_02^0}$$

注意，只有 $𝑛_𝑖 =1$的项才会真正出现在乘积的计算中。
根据这一表达式，可以首先在 $O(log⁡𝑛)$时间内计算出 𝑎的 $O(log⁡𝑛)$个 $2^𝑘$ 次幂的取值，然后花费 $O(log⁡𝑛)$ 的时间选择等于 1 的二进制位对应的幂次乘到最终结果中。这就是快速幂的迭代版本实现。

递归版本

这一过程同样可以通过递归形式实现。注意到,指数 𝑛 的二进制展开可以递归地写作

$(𝑛_𝑡𝑛_{𝑡−1}⋯𝑛_1𝑛_0)_2=2×(𝑛_𝑡𝑛_{𝑡−1}⋯𝑛_1)_2+𝑛0$

因此，幂次 $𝑎^𝑛$ 可以递归地计算为

aⁿ = 
⎧ 1,                         当 n = 0
⎨ (a^(n/2))²,                当 n 为偶数
⎩ a × (a^((n-1)/2))²,        当 n 为奇数

这就是快速幂的递归版本实现。

def fast_power_mod(a, n, m):
    """
    计算 a^n mod m 的递归实现
    
    参数:
        a: 底数
        n: 指数
        m: 模数
    
    返回:
        a^n mod m 的结果
    """
    if n == 0:
        return 1
    
    half = fast_power_mod(a, n // 2, m)
    
    if n % 2 == 0:
        return (half * half) % m
    else:
        return (a * half * half) % m

# 测试示例
print(fast_power_mod(2, 10, 1000))  # 输出: 24 (因为 2^10=1024, 1024 mod 1000 = 24)