def fast_power(a, n):
    if n == 0:
        return 1
    result = 1
    base = a
    k = n
    while k > 0:
        if k % 2 == 1:  # 或 k & 1
            result *= base
        base *= base    # 准备更高位的基数
        k //= 2         # 或 k >>= 1
    return result

快速幂算法（Fast Exponentiation） 快速幂算法是一种高效计算大整数幂的方法，其核心思想是通过二分策略将指数分解为二进制形式，将时间复杂度从朴素的O(n)降低到O(log n)。以下是逐步讲解： 问题描述 计算 \( a^n \)（a的n次幂），其中a为实数，n为非负整数。直接连乘需要n-1次乘法，当n极大时（如\( n = 10^9 \)）效率极低。快速幂通过指数n的二进制表示优化计算过程。 关键思路 二进制分解指数 ： 将指数n表示为二进制形式，例如 \( n = 13 \) 的二进制是 \( 1101_ 2 \)，即： \[ n = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \] 此时： \[ a^n = a^{13} = a^{8} \cdot a^{4} \cdot a^{0} \cdot a^{1} \] 注意：二进制位为0的项（如\( a^2 \)）被跳过。 迭代计算 ： 从低位到高位处理n的二进制位，同时维护一个变量 base （初始为a），每次迭代将 base 平方，并根据当前二进制位决定是否乘到结果中。 算法步骤 初始化 ： 结果 result = 1 基数 base = a 指数 k = n （用于迭代） 循环直到k为0 ： 检查最低位 ：若k的二进制最低位为1（即 k % 2 == 1 ），则将当前 base 乘到 result 中。 更新基数 ：将 base 平方（即 base = base * base ），为处理更高位做准备。 右移指数 ：将k右移一位（即 k = k // 2 ），相当于删除已处理的最低位。 返回结果 ：循环结束时 result 即为\( a^n \)。 示例演示（计算 \( 3^{13} \)） | 迭代次数 | k（二进制） | 最低位 | result（更新规则） | base（更新规则） | |----------|-------------|--------|----------------------------|-----------------| | 初始 | 13 (1101) | - | 1 | 3 | | 1 | 13 (1101) | 1 | 1 × 3 = 3 | 3² = 9 | | 2 | 6 (110) | 0 | 3（不乘base） | 9² = 81 | | 3 | 3 (11) | 1 | 3 × 81 = 243 | 81² = 6561 | | 4 | 1 (1) | 1 | 243 × 6561 = 1594323 | 6561²（无需计算）| 最终结果：\( 3^{13} = 1594323 \)，仅需5次乘法（朴素方法需12次）。 代码实现（Python） 复杂度分析 时间复杂度 ：O(log n)，因为n每次右移一位（二分）。 空间复杂度 ：O(1)，仅用常数变量。 应用场景 大数取模 ：在加密算法（如RSA）中计算 \( a^n \mod m \)，每一步乘法后及时取模避免溢出。 矩阵快速幂 ：求解线性递推关系（如斐波那契数列），将线性递推转化为矩阵幂运算。 算法竞赛 ：处理极大指数的常见优化手段。 通过二进制分解将乘次数降至对数级别，快速幂完美体现了“分治”思想在数学运算中的威力。