如果我问在座的各位,快速幂是什么,恐怕没几个人能答上来……
但是,快速幂这么重要的知识,怎么能不学呢?
快速幂是对于求的一种快速的算法。的解法有很多种,我们从暴力法讲起:
众所周知,的定义为b个a相乘,因此只需要用一个循环就能搞定了:
#define LL long long LL PowerMod(LL a, LL b, LL m) { int ans = 1; for (int i = 0; i < b; i++) { // 关键! ans = (ans * a) % m; } return ans; }
时间复杂度:O(b)
空间复杂度:O(1)
优点是写法简洁,缺点是速度太慢,在的数据范围下根本撑不住。
二分幂的想法如下:
如b为奇数,
如b为偶数,
因此可以写出递归代码:
LL PowerMod2(LL a, LL b, LL m) { if (b == 0) { // 递归边界 return 1; } LL mul = PowerMod2(a, b / 2, m); // 求a^(b/2) if (b & 1) { // 用位运算代替奇偶性判断 return mul * mul * a; } return mul * mul; }
时间复杂度:O(log2(b)) (当然了递归比较慢)
空间复杂度:O(log2(b)) (递归需占用内存)
优点是速度变快,缺点是需要占用空间,不过一般O(log2(b))的空间复杂度足够了。
终于到正题了!快速幂的想法如下:
先把b拆成二进制
再对每一位进行分解:
如果为1,就算,
否则,就不算。
举个例子:由于 ,所以
而我们直接用一个循环统计就行了。
不多说,直接上代码:
LL PowerMod3(LL a, LL b, LL m) { LL ans = 1; a %= m; // 预处理 for (; b > 0; b /= 2) { // 获得每一位 if (b & 1) { // 如果这一位是一 ans = ans * a % m; } a = a * a % m; // 注:a * a不是原来的a * a了!想想是什么? } return ans; }
1、这边的都是模板……(废话)
3、你们知道只算幂怎么办了吧?(废话)
4、那你们有没有看到没有2呢?(啊?)