按二进制拆

朴素地算 $a^{13}$ 要连乘 13 次，指数一大就慢得离谱。快速幂的核心思想是：把指数按二进制拆开。任何整数都能唯一写成 2 的幂之和，因为它本来就是二进制存的。比如 $13=(1101{)}_2=8+4+1$，于是

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

而 $a^1,a^2,a^4,a^8$ 这一串，每个都是前一个的平方，一路平方就能全拿到。指数的二进制里哪一位是 1，就把对应的那一项乘进答案。

// 看 13 的二进制哪几位是 1
int n = 13;
while (n) {
    cout << (n & 1);  // 取最低位
    n >>= 1;          // 右移一位，相当于除以 2
}
// 从低位到高位输出 1 0 1 1

原来要 $n$ 次乘法，现在只需约 ${\log }_{2}n$ 次。$n=10^9$ 时朴素法要十亿次，快速幂只要 30 次左右。坑：用 n & 1 判断奇偶、n >>= 1 除以 2，注意负指数要单独处理。