快速幂算法 快速幂算法是一种高效计算大整数幂的方法，特别适用于模幂运算（如计算 \( a^b \mod m \)）。其核心思想是通过二分降幂，将时间复杂度从朴素的 \( O(b) \) 优化到 \( O(\log b) \)。 问题描述 计算 \( a^b \)，其中 \( a \) 和 \( b \) 均为非负整数（通常 \( b \) 很大，例如 \( b \geq 10^9 \)）。若直接进行 \( b \) 次乘法，时间成本过高。快速幂利用幂的二进制分解，将计算次数降至对数级。 解题过程 步骤1：理解幂的二进制分解 任意正整数 \( b \) 可以表示为二进制形式，例如 \( b = 13 \) 的二进制是 \( 1101_ 2 \)，即： \[ 13 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \] 因此： \[ a^{13} = a^{8} \cdot a^{4} \cdot a^{1} \] 注意：二进制位为0的项（如 \( a^{2} \)）被跳过。 步骤2：迭代计算思路 初始化 ：设结果 \( res = 1 \)，底数 \( base = a \)，指数 \( n = b \)。 循环（当 \( n > 0 \) 时） ： 若 \( n \) 的当前最低位为1（即 \( n \mod 2 = 1 \)），则将 \( res \) 乘以当前的 \( base \)。 更新 \( base = base \times base \)（相当于计算 \( a^{2^k} \)）。 将 \( n \) 右移一位（即 \( n = n // 2 \)），相当于处理下一个二进制位。 终止 ：当 \( n = 0 \) 时，\( res \) 即为 \( a^b \)。 步骤3：示例演示（计算 \( 3^{13} \)） 初始：\( res = 1, base = 3, n = 13 \)（二进制 1101 ） 第1轮 （\( n = 13 \)）： \( n \) 最低位为1：\( res = 1 \times 3 = 3 \) 更新 \( base = 3 \times 3 = 9 \) 右移 \( n = 13 // 2 = 6 \)（二进制 110 ） 第2轮 （\( n = 6 \)）： 最低位为0：\( res \) 不变（仍为3） 更新 \( base = 9 \times 9 = 81 \) 右移 \( n = 6 // 2 = 3 \)（二进制 11 ） 第3轮 （\( n = 3 \)）： 最低位为1：\( res = 3 \times 81 = 243 \) 更新 \( base = 81 \times 81 = 6561 \) 右移 \( n = 3 // 2 = 1 \)（二进制 1 ） 第4轮 （\( n = 1 \)）： 最低位为1：\( res = 243 \times 6561 = 1594323 \) 更新 \( base = 6561^2 \) 右移 \( n = 0 \)，结束。 结果：\( 3^{13} = 1594323 \)。 步骤4：加入模运算（计算 \( a^b \mod m \)） 在加密算法中常需计算模幂（如 RSA 算法）。只需在每一步乘法后取模即可： 修改更新规则： \( res = (res \times base) \mod m \) \( base = (base \times base) \mod m \) 示例：计算 \( 3^{13} \mod 1000 \) 第1轮：\( res = 3, base = 9 \) 第2轮：\( res = 3, base = 81 \) 第3轮：\( res = (3 \times 81) \mod 1000 = 243, base = 6561 \mod 1000 = 561 \) 第4轮：\( res = (243 \times 561) \mod 1000 = 136323 \mod 1000 = 323 \) 结果：\( 3^{13} \mod 1000 = 323 \)。 关键点总结 时间复杂度 ：\( O(\log b) \)，因每次循环指数 \( n \) 减半。 适用场景 ：大数幂运算、模幂计算（数论、密码学）。 扩展 ：可递归实现（分治思想：\( a^b = a^{b/2} \times a^{b/2} \)），但迭代版本更节省栈空间。