简介

快速幂算法相信很多OIer都已经掌握了，尽管对于初学者来说这名称高级得似乎很难懂，但是确实是非常好理解、非常简便的算法了。

推导

首先，是大部分的算法都需要经过的数学推导环节。

对于 $ n^m $ 的式子，举其中一个例子 $ 2^8 $ 进行说明。

根据幂的意义和运算规则，可以得出：$$ 2^8 = { ( 2 \times 2 ) } ^ { \frac{8}{2} } = { [ ( 2 \times 2 ) \times ( 2 \times 2 ) ] } ^ { \frac{4 }{2} } = { [ ( 2 \times 2 \times 2 \times 2 ) \times ( 2 \times 2 \times 2 \times 2 ) ] } ^ { \frac{2}{2} } = { ( 16 \times 16 ) } ^ 1 = 256 $$

很复杂对吧，但是不难注意到：每次将底数 $ n $ 自乘一次，即 $ n \times n $ ，同时指数 $ m \div 2 $ ，重复以上步骤直到指数为 $ 1 $ ，这就是快速幂算法了。

但是，我们漏掉了一个特殊情况： $ n $ 的奇次幂。

对于 $ 2^3 $ 我们要如何处理呢？很简单，其展开为： $ 2 \times 2 \times 2 $ ，分离出一项，后面不变：$$ 2^3 = 2 \times 2^2 = 2 \times 4 = 8 $$

后面的底数自乘、幂次除以2与偶次幂情况相同，即：先将答案乘一遍底数，幂次减1，再考虑偶次幂的情况即可。

代码实现

实现起来也很简便：

// 快速幂算法 
int fastPow(int n, int m) {
	int ans = 1;  // 1*any=self 0*any=0
	
	while (m >= 1) {
		if (m % 2 == 1) {  // 奇数情况
			m -= 1;  // 分离项后幂次-1 
			ans *= n;  // 答案乘分离出来的原底数 
			m /= 2;  // 幂次除以2 
			n *= n;  // 底数自乘 
		} else {  // 偶次幂
			n *= n;  // 底数自乘
			m /= 2;  // 幂次除以2 
		} 
	}
	 
	return ans;  // 返回答案 
}

优化

因为 m >= 1 相当于 m > 0 ，且有一段重复代码可省略：

m /= 2;  // 幂次除以2 
n *= n;  // 底数自乘 

并且 m % 2 == 1 的判断是否为奇数的代码可以改为位运算 m & 1 == 1 ； m /= 2 可以改为位运算 m = m >> 1 ，m >>= 1，因为右移运算符自动向下取整（自动舍去末位1），因此此代码可优化为：

// 快速幂算法 
int fastPow(int n, int m) {
	int ans = 1;  // 1*any=self 0*any=0
	
	while (m) {
		if (m & 1) ans *= n;  // 答案乘分离出来的原底数 
		n *= n;  // 底数自乘 
		m >>= 1;  // 幂次除以2 
	}
	 
	return ans;  // 返回答案 
} 

再次对比一下普通幂算法：

// 普通幂算法
int pow(int n, int m) {
	int ans = 1;
	for (int i = 0; i < m; i++) ans *= n;
	return ans;
} 

复杂度由 $ O(m) $ （普通幂）降为了 $ O( \log_{2}{m} ) $ （快速幂每次运算指数都右移一位，总循环次数为指数在二进制下的位数，即 $ \log_{2}{m} $ ）。

取模

快速幂算法一般不会单独使用，配合着大规模数据的取模使用。

首先要知道：$ (a \times b) \% p = (a \% p \times b \% p) \% p $ ，偶数次幂中将 $ a \times b $ 看作 $ n \times n $ ，奇数次幂则为 $ ans * n $ （分离出的单独的原底数）

// 快速幂算法（取模） 
int fastPow(int n, int m, int p) {
	int ans = 1;
	
	while (m) {
		if (m & 1) ans = ans * n % p;  // 答案乘分离出来的原底数并取模的结果
		n = n * n % p;  // 底数乘以自己取模后的结果
		m >>= 1;  // 幂次除以2 
	}
	 
	return ans % p;  // 返回答案取模后的结果
} 

验证

接下来就是大伙喜闻乐见的代码正确性验证的环节了：

#include <bits/stdc++.h>
using namespace std;

// 快速幂算法 
int fastPow(int n, int m) {
	int ans = 1;  // 1*any=self 0*any=0
	
	while (m) {
		if (m & 1) ans *= n;  // 答案乘分离出来的原底数 
		n *= n;  // 底数自乘 
		m >>= 1;  // 幂次除以2 
	}
	 
	return ans;  // 返回答案 
} 

// 普通幂算法
int pow(int n, int m) {
	int ans = 1;
	for (int i = 0; i < m; i++) ans *= n;
	return ans;
} 

int main() {
	cout << fastPow(5, 7) << endl << pow(5, 7) << endl;

    return 0;
}

完美！

模板题

趁热打铁，A一道模板题吧：P1226 【模板】快速幂 – 洛谷

直接复制以上代码即可AC：记录详情 – 洛谷