快速幂

问题

在 $O(\log{b})$ 时间内求幂值 $a^b$ ，结果对 $MOD$ 取余。

代码

const int MOD = 1000000007;

int qpw(int a, int b) {  // Quick power for a^b.
    int ans = 1;
    while (b) {
        if (b & 1) ans = 1ll * ans * a % MOD;
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return ans;
}