快速幂算法（模重复平方法）

字数 2577 2025-11-04 20:48:20

快速幂算法（模重复平方法）

题目描述
快速幂算法是一种高效计算大数幂运算的方法，特别是当指数非常大时（比如计算 a^n，其中 n 是一个非常大的整数）。常规的连乘方法时间复杂度为 O(n)，而快速幂算法可以将其优化到 O(log n)。该算法在密码学、大数运算等场景中应用广泛。

解题思路
快速幂算法的核心思想是分治和二进制思想。它利用幂的二进制表示，将指数 n 分解为多个 2 的幂次之和，从而将计算 a^n 转化为计算一系列 a 的平方幂的乘积。

详细步骤

将指数 n 转换为二进制形式
这是理解算法的基础。例如，计算 3^13。
指数 13 的二进制表示为 1101。
13 = 1 * 2³ + 1 * 2² + 0 * 2¹ + 1 * 2⁰ = 8 + 4 + 0 + 1
分解幂的表达式
根据幂的运算法则，a^(m+n) = a^m * a^n。
因此，3^13 = 3^(8+4+1) = 3^8 * 3^4 * 3^1
注意，我们跳过了对应二进制位为 0 的项（3^2，因为二进制第二位是0）。

算法的迭代过程
我们不需要预先计算出所有的 3^(2^k)，而是可以通过迭代的方式，从最低位（或最高位）开始，逐步计算。

方法一：从低位到高位（更常用）
我们维护两个变量：

base：表示当前位的权重，即 a^(2^k)。在迭代过程中，base 会不断平方。
result：存储最终结果。当遇到指数 n 的二进制位为 1 时，就将当前的 base 乘入 result。

计算 3^13 的步骤：
初始化：result = 1, base = 3, n = 13

步骤	n (二进制)	当前二进制位 (n % 2)	操作说明	`result` 更新	`base` 更新 (为下一步准备)	n 更新
初始	1101	-	-	1	3	13
1	1101	1 (最低位)	当前位是1，将 `base` (3^1) 乘入 `result`	`result = 1 * 3 = 3`	`base = 3 * 3 = 9` (即 3^2)	n // 2 = 6
2	110	0	当前位是0，不乘入 `result`	`result` 保持 3	`base = 9 * 9 = 81` (即 3^4)	n // 2 = 3
3	11	1	当前位是1，将 `base` (3^4) 乘入 `result`	`result = 3 * 81 = 243`	`base = 81 * 81 = 6561` (即 3^8)	n // 2 = 1
4	1	1	当前位是1，将 `base` (3^8) 乘入 `result`	`result = 243 * 6561 = 1594323`	-	n // 2 = 0
结束	0	-	n 为 0，循环结束。`result` 即为最终结果 1594323。	-	-	-

核心代码（非递归版本）

def fast_power(a, n):
    result = 1
    base = a
    # 当指数 n 还大于0时继续循环
    while n:
        # 如果 n 的当前二进制位是 1
        if n & 1: # 等价于 n % 2 == 1
            result *= base
        # base 平方，为下一位做准备
        base *= base
        # n 右移一位，相当于 n //= 2
        n //= 2 # 或者使用位运算 n >>= 1
    return result

处理取模情况
在实际问题中（如计算斐波那契数列、RSA加密），常常需要对一个很大的结果取模（a^n % mod）。快速幂算法可以很容易地结合取模运算，因为模运算满足分配律：(a * b) % mod = ((a % mod) * (b % mod)) % mod。

带模运算的快速幂代码

def fast_power_mod(a, n, mod):
    result = 1
    base = a % mod # 先取模，防止初始a过大
    while n:
        if n & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        n //= 2
    return result

总结
快速幂算法的精髓在于利用指数的二进制表示，将 O(n) 次乘法优化为 O(log n) 次。其步骤可概括为：

初始化结果 result 为 1，基数 base 为 a。
循环直到指数 n 为 0：
- 检查 n 的最低位是否为 1（n & 1），如果是，则将当前的 base 乘入 result。
- 将 base 平方。
- 将 n 右移一位（除以 2）。
返回 result。

这种方法极大地提升了大数幂运算的效率。

快速幂算法（模重复平方法）题目描述快速幂算法是一种高效计算大数幂运算的方法，特别是当指数非常大时（比如计算 a^n，其中 n 是一个非常大的整数）。常规的连乘方法时间复杂度为 O(n)，而快速幂算法可以将其优化到 O(log n)。该算法在密码学、大数运算等场景中应用广泛。解题思路快速幂算法的核心思想是分治和二进制思想。它利用幂的二进制表示，将指数 n 分解为多个 2 的幂次之和，从而将计算 a^n 转化为计算一系列 a 的平方幂的乘积。详细步骤将指数 n 转换为二进制形式这是理解算法的基础。例如，计算 3^13。指数 13 的二进制表示为 1101。 13 = 1 * 2³ + 1 * 2² + 0 * 2¹ + 1 * 2⁰ = 8 + 4 + 0 + 1 分解幂的表达式根据幂的运算法则，a^(m+n) = a^m * a^n。因此，3^13 = 3^(8+4+1) = 3^8 * 3^4 * 3^1 注意，我们跳过了对应二进制位为 0 的项（3^2，因为二进制第二位是0）。算法的迭代过程我们不需要预先计算出所有的 3^(2^k)，而是可以通过迭代的方式，从最低位（或最高位）开始，逐步计算。方法一：从低位到高位（更常用）我们维护两个变量： base ：表示当前位的权重，即 a^(2^k)。在迭代过程中， base 会不断平方。 result ：存储最终结果。当遇到指数 n 的二进制位为 1 时，就将当前的 base 乘入 result 。计算 3^13 的步骤：初始化： result = 1 , base = 3 , n = 13 | 步骤 | n (二进制) | 当前二进制位 (n % 2) | 操作说明 | result 更新 | base 更新 (为下一步准备) | n 更新 | | :--- | :--------- | :------------------- | :----------------------------------------------------------------------- | :------------------------------- | :------------------------- | :----- | | 初始 | 1101 | - | - | 1 | 3 | 13 | | 1 | 1101 | 1 (最低位) | 当前位是1，将 base (3^1) 乘入 result | result = 1 * 3 = 3 | base = 3 * 3 = 9 (即 3^2) | n // 2 = 6 | | 2 | 110 | 0 | 当前位是0，不乘入 result | result 保持 3 | base = 9 * 9 = 81 (即 3^4) | n // 2 = 3 | | 3 | 11 | 1 | 当前位是1，将 base (3^4) 乘入 result | result = 3 * 81 = 243 | base = 81 * 81 = 6561 (即 3^8) | n // 2 = 1 | | 4 | 1 | 1 | 当前位是1，将 base (3^8) 乘入 result | result = 243 * 6561 = 1594323 | - | n // 2 = 0 | | 结束 | 0 | - | n 为 0，循环结束。 result 即为最终结果 1594323。 | - | - | - | 核心代码（非递归版本）处理取模情况在实际问题中（如计算斐波那契数列、RSA加密），常常需要对一个很大的结果取模（a^n % mod）。快速幂算法可以很容易地结合取模运算，因为模运算满足分配律： (a * b) % mod = ((a % mod) * (b % mod)) % mod 。带模运算的快速幂代码总结快速幂算法的精髓在于利用指数的二进制表示，将 O(n) 次乘法优化为 O(log n) 次。其步骤可概括为：初始化结果 result 为 1，基数 base 为 a。循环直到指数 n 为 0：检查 n 的最低位是否为 1（ n & 1 ），如果是，则将当前的 base 乘入 result 。将 base 平方。将 n 右移一位（除以 2）。返回 result 。这种方法极大地提升了大数幂运算的效率。