快速幂算法详解

快速幂（Fast Exponentiation 或 Exponentiation by Squaring）是一种高效计算大数幂运算的算法，时间复杂度为 O(log n)，比普通的 O(n) 逐次乘法快得多。

一、快速幂基于以下数学原理：

快速幂算法的核心思想是通过分治策略和平方操作来减少计算次数。下面我将详细解释这两种情况的数学原理：

1. 当指数为偶数时：aⁿ = (aⁿᐟ²)²

数学推导：​​

• 当 n 是偶数时，可以表示为 n = 2k（其中 k 是整数）
• 因此：
  aⁿ = a²ᵏ = (aᵏ)²
  即：​aⁿ = (aⁿᐟ²)²​

​实际意义：​​

• 计算 aⁿ 时，先计算 aⁿᐟ²（即 aᵏ），然后将其结果平方
• 这样将问题规模减半，减少了乘法次数

​示例：计算 2¹⁰​

• 10 是偶数 → 2¹⁰ = (2⁵)²
• 先计算 2⁵ = 32
• 再平方：32² = 1024
• 原本需要 9 次乘法（2×2×...×2），现在只需 5 次（2⁵算4次 + 1次平方）

---

2. 当指数为奇数时：aⁿ = a × aⁿ⁻¹ = a × (a⁽ⁿ⁻¹⁾ᐟ²)²

​数学推导：​​

• 当 n 是奇数时，可以表示为 n = 2k + 1
• 因此：
  aⁿ = a²ᵏ⁺¹ = a × a²ᵏ = a × (aᵏ)²
  即：​aⁿ = a × (a⁽ⁿ⁻¹⁾ᐟ²)²​

​实际意义：​​

• 先减 1 变成偶数（n-1），然后对半拆分
• 最后多乘一个 a 来补回减去的 1

​示例：计算 3⁷​

• 7 是奇数 → 3⁷ = 3 × 3⁶
• 6 是偶数 → 3⁶ = (3³)²
• 计算 3³ = 27
• 平方：27² = 729
• 最终：3 × 729 = 2187
• 原本需要 6 次乘法，现在只需 4 次（3³算2次 + 1次平方 + 1次乘3）

3.递归实现

def fast_pow(a, n):if n == 0:return 1elif n % 2 == 0:  # 偶数half = fast_pow(a, n // 2)return half * halfelse:  # 奇数return a * fast_pow(a, n - 1)

4.迭代实现

def fast_pow(a, n):result = 1          # 初始化结果为1（因为任何数的0次方都是1）while n > 0:        # 当指数n大于0时继续循环if n % 2 == 1:  # 如果当前n是奇数（二进制最后一位为1）result *= a  # 将当前的a乘入结果a *= a          # a平方（为下一轮做准备）n = n // 2      # n右移一位（相当于n//2）return result       # 返回最终结果

5.带模运算的快速幂

在计算大数幂时通常需要取模：

def fast_pow_mod(a, n, mod):result = 1a = a % mod  # 先取模防止溢出while n > 0:if n % 2 == 1:result = (result * a) % moda = (a * a) % modn = n // 2return result

应用场景

1. 密码学（RSA等加密算法）
2. 大数计算
3. 矩阵快速幂（用于动态规划优化）
4. 计算组合数取模

快速幂算法将幂运算的时间复杂度从O(n)降低到O(log n)，对于大指数计算非常高效。