快速幂

一句话理解

快速幂：二进制拆指数，O(log e)。

为什么要学

求 a^e % m。

讲解

底数平方，指数右移。

例子

long long qpow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

和倍增一样拆二进制。

常见错误

• e=0 应返回 1。
• 中间不模。