• 快速幂是一种高效计算幂运算的算法，核心思想是将指数进行二进制分解，从而将计算复杂度从 O(n) 降低到 O(log n)。

---

算法原理：

计算 a^b，将 b 写成二进制形式，例如 b = 13 (二进制 1101)，则 a^13 = a^(8) * a^(4) * a^(1)。通过反复平方 a 并检查二进制位，可快速得到结果。

迭代实现（常用）：

// 计算 a^b
long long quick_pow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a;  // 当前二进制位为1，乘上对应的a
        a = a * a;                 // a平方，准备下一位
        b >>= 1;                   // 右移一位
    }
    return res;
}

取模版本（计算 a^b mod p）：

long long quick_pow_mod(long long a, long long b, long long p) {
    long long res = 1 % p;         // 注意 p=1 时 res=0
    while (b > 0) {
        if (b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

递归实现：

long long quick_pow(long long a, long long b) {
    if (b == 0) return 1;
    long long half = quick_pow(a, b / 2);
    if (b % 2 == 0) return half * half;
    else return half * half * a;
}

时间复杂度：​ O(log b)，其中 b 是指数。

应用场景：

1. 大数幂取模（如加密算法、组合数取模）。
2. 矩阵快速幂（加速线性递推，如斐波那契数列）。
3. 求逆元（费马小定理 a^(p-2) mod p，p 为质数）。

示例：​ 计算 3^13

13 的二进制为 1101，过程：

初始 res=1, a=3, b=13

b=13: 最低位1 → res=3, a=9, b=6

b=6: 最低位0 → res=3, a=81, b=3

b=3: 最低位1 → res=243, a=6561, b=1

b=1: 最低位1 → res=1594323, a=6561^2, b=0

结果为 1594323。

快速幂是算法竞赛中的基础且重要的技巧，尤其在涉及大指数和取模运算时必不可少。