目的

很快地求出 a^b

正常使用循环暴力相乘的话,需要运算 b 次,复杂度约为 \mathrm{O}(b),显然效率太低了。

所以我们要引入复杂度为 \mathrm{O}(\log(b)) 的快速幂。

我们都知道 a^{x}a^{y}=a^{x+y}

快速幂算法的核心思想就是每一步都把指数分成两半,而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小,所需要执行的循环次数也变小,而最后表示的结果却一直不会变。

例如,要求 a^{11}

11 的二进制为 1011

11 = 2^3 \times 1 + 2^2 \times 0 + 2^1 \times 1 + 2^0 \times 1

那么,a^{11}=a^{2^0+2^1+2^3}

所以我们可以将 a^{11} 转化为 a^{2^0} \times a^{2^1} \times a^{2^3} 计算。

typedef long long ll;
inline ll qpow(ll a, ll b, ll p) {
    ll r = 1 % p, base = a % p;
    while(b) {
        if (b & 1) r = r * base % p;
        base = base * base % p;
        b >>= 1;
    }
    return r;
}

徒具人形