快速幂取模算法 什么是快速幂？ 代码
快速幂应当是快速幂取模的简称
对于一般的求幂算法，求$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; }