简介
快速幂算法相信很多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:记录详情 – 洛谷
print(5**7)’print(pow(5,7))
复杂度太高,大数据直接TLE(超时)