快速幂

简单来说，快速幂（Fast Power / Binary Exponentiation） 是一种用极快速度计算 $a^b$（$a$ 的 $b$ 次方）的神仙算法。

如果你用常规的循环相乘，算 $a^b$ 需要乘 $b$ 次，当 $b$ 特别大（比如 $10^{18}$）时，程序就会直接运行超时（TLE）。而快速幂可以将时间复杂度从 $O(b)$ 降到 $O(\log b)$。

它的核心逻辑是什么？

快速幂的核心思想是：分治 + 二进制拆分。

举个例子，要计算 $2^{10}$：

传统做法（乘 10 次）

$2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$

快速幂做法（拆分指数）

我们可以把指数 $10$ 拆成二进制：$10 = (1010)_2 = 8 + 2$。

所以：

$2^{10} = 2^8 \times 2^2$

注意到 $2^8 = (((2)^2)^2)^2$ 吗？我们不需要挨个乘，只需要把底数不断做平方（自乘）：

1. $2^1 = 2$
2. $2^2 = 4$
3. $2^4 = 16$
4. $2^8 = 256$

每一次底数自乘，指数就翻倍，这让我们只用了 4 次乘法就完成了原本需要 10 次的计算！

算法规则（递归与迭代）

不管是奇数还是偶数，算法的处理逻辑如下：

• 如果指数 $b$ 是偶数：$a^b = (a^{b/2})^2$
• 如果指数 $b$ 是奇数：$a^b = a \times a^{b-1}$

由于大数乘法很容易溢出，实际应用中通常会结合取模操作（Mod），也就是求 $(a^b) \bmod m$。

参考代码（非递归迭代版）

在实际比赛或面试中，非递归（位运算）版本最受欢迎，因为它不需要栈空间开销，而且运行速度更快。

#include <iostream>

long long fast_power(long long a, long long b, long long m) {
    long long ans = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) ans = (ans * a) % m; // 如果是奇数/最低位为1
        a = (a * a) % m;                // 底数自乘
        b >>= 1;                        // b 除以 2
    }
    return ans;
}

性能对比