1.快速幂

快速幂，顾名思义，就是快速地计算 $a$ 的 $b$ 次幂。

时间复杂度为 $O(\log n)$，与朴素的 $O(n)$ 相比，效率有了极大的提高。

对于 $a^b$ 来说，$b$ 是可以拆成二进制的。

例如求 $3^{11}$，$11$ 的二进制是 $1011$，即 $11=2^3+2^1+2^0$，

那么 $3^{11}=3^{(2^3+2^1+2^0)}=3^{(2^3)}\ast 3^{(2^1)}\ast 3^{(2^0)}=3^8\ast 3^2\ast 3^1$

int quickPow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

2.快速幂取模

快速幂取模，顾名思义，就是快速地计算 $a^b\%m$ 的值。

用到的公式：

• $(a+b)\%p=(a\%p+b\%p)\%p$

• $(a-b)\%p=(a\%p-b\%p)\%p$

• $(a\ast b)\%p=(a\%p\ast b\%p)\%p$

• $(a^b)\%p=((a\%p{)}^b)\%p$

以 $3^{89}\%7$ 为例：

• $3\%7=3$

• $3^2\%7=2$

• $3^4\%7=(3^2{)}^2\%7=(3^2\%7{)}^2\%7=2^2\%7=4$

• $3^8\%7=(3^4{)}^2\%7=(3^4\%7{)}^2\%7=4^2\%7=2$

• $3^{16}\%7=(3^8{)}^2\%7=(3^8\%7{)}^2\%7=2^2\%7=4$

• $3^{32}\%7=(3^{16}{)}^2\%7=(3^{16}\%7{)}^2\%7=4^2\%7=2$

• $3^{64}\%7=(3^{32}{)}^2\%7=(3^{32}\%7{)}^2\%7=2^2\%7=4$

• $3^{89}\%7=3^{(1011001)}\%7=(3^{64}\ast 3^{16}\ast 3^8\ast 3^1)\%7=(4\ast 4\ast 2\ast 3)\%7=96\%7=5$

int quickPow(int a, int b, int m)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}