快速幂取模算法

什么是快速幂？

快速幂应当是快速幂取模的简称

对于一般的求幂算法，求$a^b\,mod\,m$，即使用循环b次的方法，复杂度是$O(b)$的，当b很大的时候，这种算法就会显得十分缓慢。

快速幂是基于以下明显的事实：

$${a^b} equiv {(a^2)^{frac{b}{2}}} pmod{m}quad b is even$$

$${a^b} equiv {(a^2)^{frac{b}{2}}*a} pmod{m}quad b is odd$$

那么我们得到这样一个算法，如果当前的$b$是偶数，那么$a$就取平方，否则取$a^2*a$，每次$b=b/2$。算法的复杂度是$O(log b)$。

代码

递归版 

typedef long long LL;
//calculate a^b%m
LL Pow(LL a,LL b,LL m) {
    if (b == 0)
        return 1;
    if (b & 1)
        return Pow(a * a, b >> 1, m) * a;
    else
        return Pow(a * a, b >> 1, m);
}

非递归版

typedef long long LL;
//calculate a^b%m
LL Pow(LL a,LL b,LL m) {
    LL res = 1;
    while (b) {
        if (b & 1)res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}