幂运算

幂运算是一种幂的运算，它有一个性质：同底数幂相乘，底数不变，指数相加

求幂运算的朴素做法 $O (k)$

假设此时我们需要求底为a，指数为k的幂的值，即求 $res = a^k$ ，那么我们很容易想到最直接的做法：令 $r e s = 1$ ，让res乘以k次a即可得到答案。

代码：

int power(int a,int k){
	int res = 1;
	while(k --) res *= a;
	return res;
}

容易看出，它总共进行了k次运算，因此时间复杂度为 $O (k)$

快速幂 $O (l o g k)$

有时候当要求的次方大于一定值时，用朴素做法求幂就会显得效率很低，那么有没有什么方法可以快速求幂呢？
这就需要用到上方的性质：同底数幂相乘，底数不变，指数相加
假设我们需要求 $3^7$ ，那么我们可以分为 $3 ? 3 ? 3 ? 3 ? 3 ? 3 ? 3$ ，也可以等于 $3^2 * 3^2 * 3^2 * 3$ ，原因是它们的指数之和为 $7$ ，那么我们就会想到二进制优化
$7 = 4 + 2 + 1 = 2^2 + 2^1 + 2^0 = 111_2$
于是 $3^7 = 3^{111_2}$
因此我们只需要处理出指数k的二进制表示及每个二进制数下的乘数即可。

如果k为0，停止运算
每当 $k$ 的最低位数为0时， $r e s$ 不进行运算，为1时， $r e s = r e s ? a$
然后将 $a = a ? a$ (每个二进制数下的乘数)
最后 $k > > = 1 (k = k / 2)$

求 $3^7(3^{111_2})$ ：
$r e s = 1$

$k! = 0$
k的最低位为1, $r e s = r e s ? a = 1 ? 3 = 3$ ；
$a = a ? a = 9$
$k > > = 1$ $k = k / 2 = 3(111_2 >> 1 == 11_2)$

$k! = 0$
k的最低位为1, $r e s = r e s ? a = 3 ? 9 = 27$ ；
$a = a ? a = 81$
$k > > = 1$ $k = k / 2 = 1,(11_2 >> 1 == 1_2))$

$k! = 0$
k的最低位为1, $r e s = r e s ? a = 27 ? 81 = 2187$ ；
$a = a ? a = 6561$
$k > > = 1$ $k = k / 2 = 0,(1_2 >> 1 == 0_2))$

$k = = 0$
返回 $r e s = 2187$

代码

int qmi(int a,int k){ // 求a的k次方
	int res = 1;
	while(k){
		if(k & 1) res = res * a;
		a = a * a;
		k >>= 1;
	}
	return res;
}

含求模运算的代码

int qmi(int a,int k,int p){ // 求a的k次方模p
	int res = 1;
	while(k){
		if(k & 1) res = (long long)res * a % p;
		a = (long long)a * a % p;
		k >>= 1;
	}
	return res;
}