快速幂算法

快速幂算法是一种用于高效计算大数乘方的算法。当我们需要计算a的n次方（a^n）时，最直接的方法是进行n-1次乘法，时间复杂度为O(n)。然而，当指数n非常大时（例如在密码学或大数计算中，n可能是一个几百位的大数），这种线性时间的方法就变得不可行。快速幂算法通过将指数n进行二进制分解，能将时间复杂度降低到O(log n)。

核心思想

快速幂算法的核心思想是“二分”和“倍增”。它利用了幂运算的一个基本性质：a^(m+n) = a^m * a^n。更重要的是，它通过将指数n表示为二进制形式，将计算过程转化为一系列平方运算。例如，a^13 可以表示为 a^(1101)₂，即 a^(8+4+1) = a^8 * a^4 * a^1。

解题过程详解

让我们通过计算 3 的 13 次方 (3^13) 来一步步理解快速幂算法。13 的二进制表示是 1101。

步骤 1：初始化变量
我们需要初始化三个关键变量：

• base（基数）：初始值为我们要计算的底数 a。在计算过程中，base 会不断自我平方，代表 a^(2^k)，其中 k 是当前二进制位的位数。
• exponent（指数）：即 n，我们将其视为一个二进制数来处理。在迭代过程中，我们会不断地将其右移（除以2），以检查它的每一位。
• result（结果）：初始值为 1。最终，它将包含我们的计算结果。

对于 3^13：

• base = 3
• exponent = 13 (二进制 1101)
• result = 1

步骤 2：循环处理指数的每一位
只要指数 exponent 还大于 0，我们就继续循环。在每一次循环中，我们做两件事：

1. 检查当前最低位（Least Significant Bit, LSB）：我们检查指数 exponent 的当前最低位是否为 1。方法是判断 (exponent % 2) == 1 或者使用位运算 (exponent & 1) == 1。

   • 如果最低位是 1：这意味着当前二进制位对最终结果有贡献。因此，我们需要将当前的 base 乘到 result 上。
   • 如果最低位是 0：则跳过，不进行乘法。

2. 更新基数并右移指数：

   • 更新基数 (base): 将 base 自我平方 (base = base * base)。这实际上是在为处理下一个更高位的二进制位做准备。因为下一个二进制位的权重是当前位的两倍，所以对应的幂值应该是当前的平方（例如，从 a^2 变成 a^4）。
   • 右移指数 (exponent)：将 exponent 向右移动一位（相当于除以 2 并向下取整），即 exponent = exponent // 2 或使用位运算 exponent = exponent >> 1。这样我们就移除了已经处理过的最低位，可以开始处理下一位了。

步骤 3：逐步演算 3^13

让我们一步步跟踪循环过程：

• 迭代 1:

  • 当前 exponent = 13 (二进制 1101)。最低位是 1。
  • 操作 1 (检查最低位)：因为最低位是 1，所以将当前 base (3) 乘到 result 上。result = 1 * 3 = 3。
  • 操作 2 (更新)：
    • base 自我平方：base = 3 * 3 = 9 (现在 base 代表 3^2)。
    • 右移 exponent：exponent = 13 // 2 = 6 (二进制 110)。

• 迭代 2:

  • 当前 exponent = 6 (二进制 110)。最低位是 0。
  • 操作 1 (检查最低位)：因为最低位是 0，所以 result 保持不变，仍为 3。
  • 操作 2 (更新)：
    • base 自我平方：base = 9 * 9 = 81 (现在 base 代表 3^4)。
    • 右移 exponent：exponent = 6 // 2 = 3 (二进制 11)。

• 迭代 3:

  • 当前 exponent = 3 (二进制 11)。最低位是 1。
  • 操作 1 (检查最低位)：因为最低位是 1，所以将当前 base (81) 乘到 result 上。result = 3 * 81 = 243。
  • 操作 2 (更新)：
    • base 自我平方：base = 81 * 81 = 6561 (现在 base 代表 3^8)。
    • 右移 exponent：exponent = 3 // 2 = 1 (二进制 1)。

• 迭代 4:

  • 当前 exponent = 1 (二进制 1)。最低位是 1。
  • 操作 1 (检查最低位)：因为最低位是 1，所以将当前 base (6561) 乘到 result 上。result = 243 * 6561 = 1594323。
  • 操作 2 (更新)：
    • base 自我平方：base = 6561 * 6561 (我们不再需要这个值)。
    • 右移 exponent：exponent = 1 // 2 = 0。

• 循环结束：此时 exponent 为 0，循环终止。最终结果 result = 1594323。

我们可以验证一下：3^13 确实等于 1594323。

算法实现（Python）

def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        # 如果当前最低位为1，则将当前的base乘入结果
        if exponent & 1:
            result *= base
        # base 自我平方（倍增）
        base *= base
        # 指数右移一位（处理下一位）
        exponent = exponent >> 1
    return result

# 示例：计算 3^13
print(fast_power(3, 13)) # 输出：1594323

总结

快速幂算法的精髓在于将线性次的乘法（O(n)）通过二进制的思想优化到了对数次（O(log n)）。其关键步骤是：

1. 初始化 result=1, base=a, exponent=n。
2. 循环直到 exponent 为 0：
   • 若 exponent 的当前最低位为 1，则 result 乘以当前的 base。
   • base 自我平方。
   • exponent 右移一位。
3. 返回 result。

这个方法不仅高效，而且可以很容易地扩展到大数取模运算（如计算 (a^n) % mod），这在竞赛和面试中非常常见。只需在每次乘法后立即取模即可防止数值溢出。