快速冪（Exponentiation by squaring，平方求冪）是一種簡單而有效的小算法战惊，它可以以的時(shí)間復(fù)雜度計(jì)算乘方≡矗快速冪不僅本身非常常見吞获，而且后續(xù)很多算法也都會用到快速冪（龜速加也是此思想）。
思想是二分思想：
計(jì)算a的n次方谚鄙，如果n是偶數(shù)（不為0）各拷，那么就先計(jì)算a的n/2次方，然后平方闷营；如果n是奇數(shù)烤黍，那么就先計(jì)算a的n-1次方，再乘上a傻盟；遞歸出口是a的0次方為1速蕊。
遞歸快速冪的思路非常自然，代碼也很簡單（直接把遞歸方程翻譯成代碼即可）：
static int quickMi(int a, int k) {
int res = 1;
//a %= mod; //a可能比較大 a*a 可能會爆int直接進(jìn)行一次取模娘赴；有些地方可以加规哲，有些可以不加
while (k != 0) {
//如果是奇數(shù)的話
if ((k & 1) != 0) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
