快速幂模板

​ 给定 $a, b$ 算出 $a ^ b$ 的结果。

​ 传统方法是直接将 $a$ 乘 $b$ 次，但是算法复杂度是 $O(b)$，如果遇到 $b$ 很大的情况就很慢。

​ 下面是快速幂的作用原理：

​ 假设 $b$ 是偶数，那么：
$$ a^b = a ^ {2\frac{b}{2}} = (a^2)^{\frac{b}{2}} $$
​ 也就是说，将 $a$ 重新赋值为 $a ^ 2$ ，$b$ 重新赋值为 $\frac{b}{2}$。

​ 假设 $b$ 是奇数，那么：
$$ a ^ b = a·a^{b - 1} = a · (a^2)^{\frac{b-1}{2}} $$
​ 将这个被“挤”出来的 $a$ 给 $res$ 吸收即可。

​ 一直重复上述操作，直至 $b = 0$ 即可结束。时间复杂度降到 $O(\log b)$。

代码

typedef long long ll;

int qmi(int a, int b, int p){
    int res = 1;
    while (b){
        if (b & 1)  res = (ll) res * a % p;
        b >>= 1;
        a = (ll) a * a % p;
    }

    return res;
}