算法背景

在计算大功率指数幂 $a^n$ 时，最直观的方法是将底数 $a$ 连续相乘 $n$ 次。这种朴素算法的时间复杂度为 $O(n)$。当指数 $n$ 非常大（例如达到 $10^{18}$ 级别）时，线性时间的效率将无法满足性能要求。为了优化计算过程，我们通常采用快速幂（Fast Exponentiation）算法，利用分治思想将复杂度降低至 $O(\log n)$。

核心原理

快速幂的核心在于指数的二进制拆分。根据幂运算的性质 $a^{b+c} = a^b \cdot a^c$，我们可以将指数 $n$ 表示为若干个 2 的幂次之和。例如，若要计算 $a^{13}$，由于 $13$ 的二进制表示为 $(1101)_2$：

$$13 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 8 + 4 + 1$$

因此：

$$a^{13} = a^8 \cdot a^4 \cdot a^1$$

在计算过程中，我们可以通过倍增（Doubling）的方式，从 $a^1$ 开始，依次计算出 $a^2, a^4, a^8, a^{16} \dots$。每一项都是前一项的平方，计算这些项仅需 $\log n$ 次乘法。通过遍历 $n$ 的二进制位，如果某一位为 1，则将对应的倍增项乘入最终结果。

算法实现

在实际编程中，我们通过位运算来高效地提取二进制位。以下是快速幂的基础实现逻辑：

typedef long long int64;

/**
 * 计算 base 的 power 次幂
 */
int64 compute_power(int64 base, int64 power) {
    int64 result = 1;
    while (power > 0) {
        // 如果当前二进制位为 1，累乘到结果中
        if (power & 1) {
            result = result * base;
        }
        // 底数翻倍（倍增：a -> a^2 -> a^4 ...）
        base = base * base;
        // 右移一位，处理下一个二进制位
        power >>= 1;
    }
    return result;
}

模幂运算

在算法竞赛或密码学应用（如 RSA 算法）中，直接计算结果往往会导致数值溢出。因此，通常需要对结果进行取模运算，即计算 $a^n \pmod m$。利用模运算的性质 $(a \cdot b) \pmod m = ((a \pmod m) \cdot (b \pmod m)) \pmod m$，我们可以在每一步乘法后立即取模。

/**
 * 计算 (base^power) % mod
 */
long long quick_modular_pow(long long base, long long power, long long mod) {
    long long ans = 1;
    // 预处理 base，防止初始值过大
    base %= mod;
    
    while (power > 0) {
        // 检查当前最低位是否为 1
        if (power & 1) {
            ans = (__int128)ans * base % mod; // 使用 __int128 防止中间计算溢出
        }
        // 更新底数为自身的平方并取模
        base = (__int128)base * base % mod;
        // 指数右移
        power >>= 1;
    }
    return ans;
}

逻辑演示

以下是以 $3^{10}$ 为例的执行轨迹：

1. $10$ 的二进制为 $1010$。初始 ans = 1, base = 3。
2. 第一轮：power 为 $10$（偶数），不执行乘法。base 变为 $3^2 = 9$。
3. 第二轮：power 为 $5$（奇数），ans = 1 * 9 = 9。base 变为 $9^2 = 81$。
4. 第三轮：power 为 $2$（偶数），不执行乘法。base 变为 $81^2 = 6561$。
5. 第四轮：power 为 $1$（奇数），ans = 9 * 6561 = 59049。base 变为 $6561^2$。
6. 循环结束，返回结果 $59049$。

这种方法通过跳过不必要的乘法，将复杂度严格控制在 $O(\log n)$，极大地提升了处理大数据的能力。