快速幂的想法

算 $a^b$，一个个乘要乘 $b-1$ 次，$b$ 很大就慢。快速幂的想法：与其一次翻一倍指数地慢慢加，不如"平方"着翻——先算 $a^2$，再平方得 $a^4$，再平方得 $a^8,a^{16}\dots$ 指数每次翻倍，几步就冲到很大。

从 2 开始连续平方：$2\to 4\to 16\to 256\to 65536$，即 $2^1\to 2^2\to 2^4\to 2^8\to 2^{16}$，4 步就到 $2^{16}$。一般地，把指数 $b$ 看成二进制：哪一位是 1，就把对应的那个平方项乘进答案。

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;  // 当前二进制位是 1
        a = a * a % p;                 // 底数平方
        b >>= 1;                       // 指数右移一位
    }
    return res;
}

复杂度 $O(\log b)$，$b=10^{18}$ 也只需约 60 步。常见坑：res 和 a 都要开 long long 并每步取模防溢出；b 用右移逐位处理，别漏了 a=a*a 那一步；底数先 a %= p 一下更稳。