快速幂算法

原理介绍

快速幂是一种高效计算 大整数幂取模 的算法。
朴素计算 base^exp 的时间复杂度为 O(exp)，当指数极大时（例如 exp=10^9）会严重超时。
快速幂利用 分治 思想，将时间复杂度降为 O(log exp)。

核心思想

根据指数的奇偶性进行二分递推：

  • 若 exp 为偶数：
    base^exp = (base^2)^(exp/2)
  • 若 exp 为奇数：
    base^exp = base × (base^2)^((exp-1)/2)

每次将指数减半，底数平方，从而将线性次数的乘法降为对数次。

取模运算

在实际应用中，幂的结果往往大到无法存储，因此通常结合 模运算 进行。
模运算满足：(a × b) % mod = [(a % mod) × (b % mod)] % mod，可以在每一步乘法后立即取模，防止溢出。

以下附上代码：

typedef long long ll;

// 快速幂：计算 (base^exp) % mod
ll qpow(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;          // 先对底数取模，防止后续乘法溢出
    while (exp) {
        if (exp & 1)      // 等价于 exp % 2 == 1，当前位为 1 时累乘
            res = (res * base) % mod;
        base = (base * base) % mod;  // 底数平方，对应指数减半
        exp >>= 1;        // 等价于 exp /= 2，右移一位
    }
    return res;
}