摘要：
本文主要介绍了整数快速幂、矩阵快速幂及其应用，以题为例重点展示了使用细节。
我们要计算一个整数x的n次方，即x^n，普通的方法是连乘，这里介绍一种效率非常高的计算幂运算的算法——反复平方法。
首先考虑加速幂运算的方法，如果n=2^k，则可以将x^n = ((x2)2)..，即只要做k次平方运算就可以求得x^n。然后由此我们可以想到，先将n表示为2的幂次之和，即x^n = 2k1 + 2k2 + 2k3... ，那么 x^n = x2^k1 * x2^k2 * x2^k1 ...，只需在求x2^i 的同时进行计算就好了。最终得到O(logn)的计算幂运算的算法。
比如计算x^22 = x^16 * x^4 * x^2，其中22的二进制数是10110，也就是需要反复平方3次。代码如下：
1 typedef long long ll; 2 ll qpow(ll x, ll n) { 3 ll res = 1; 4 while(n) { 5 if(n&1) 6 res = res * x; //如果二进制最低位为1，则乘上x^(2^i) 7 x = x * x; //将x平方 8 n >>= 1; //n/2 9 } 10 return res; 11 }
在实际应用中有时还需要求解x^n%mod。代码如下：
1 typedef long long ll; 2 ll qpow(ll x, ll n, ll mod) { 3 ll res = 1; 4 while(n) { 5 if(n&1) 6 res = res * x % mod; //如果二进制最低位为1，则乘上x^(2^i) 7 x = x * x % mod; //将x平方 8 n >>= 1; //n/2 9 } 10 return res; 11 }
