一、什么是快速幂
答:快速求出 (a^k mod p) 的结果! 比如 (2^100 % 7) 的结果 。没有在模前提下的快速幂意义不大,传统的(pow(a,b))就很优秀了,还用的着我来优化吗?
二、快速幂的原理
答:快速幂算法的原理是通过将指数拆分成几个因数相乘的形式,来简化幂运算。在我们计算(3^13) 的时候,普通的幂运算算法需要计算(13)次,但是如果我们将它拆分成(3^{8+4+1}) ,再进一步拆分成 只需要计算(4)次。嗯?哪来的(4)次?,别急,接着看。
这种拆分思想其实就是借鉴了二进制与十进制转换的算法思想,我们知道(13)的二进制是(1101),可以知道:
(13=1×2^3 + 1×2^2 + 0×2^1 + 1×2^0 = 8 + 4 + 1)
原理就是利用位运算里的位移“>>”和按位与“&”运算,代码中(k&1)其实就是取(k)二进制的最低位,用来判断最低位是(0)还是(1),再根据是(0)还是(1)决定乘不乘,不理解的话联系一下二进制转换的过程。
(k >>= 1)其实就是将k的二进制向右移动一位,就这样位移、取最低位、位移、取最低位,这样循环计算,直到指数(k)为(0)为止,整个过程和我们手动将二进制转换成十进制是非常相似的。
普通幂算法是需要循环指数次,也就是指数是多少就要循环计算多少次,而快速幂因为利用了位移运算,只需要算“指数二进制位的位数”次,对于(13)来说,二进制是(1101),有(4)位,就只需要计算(4)次,快速幂算法时间复杂度是(O(logn))级别,对于普通幂需要计算一百万次的来说,快速幂只需要计算(6)次,这是速度上质的飞跃,但是需要多注意溢出的问题。
三、举个栗子
把(3^{13})进行转化:
(3^{13}=3^{8+4+1}=3^8×3^4×3^1)
如果我们能求出(3^1),(3^4),(3^8),我们就可以求出最后的(3^{13}),因为把它们乘在一起就可以了嘛。那怎么求呢?
(3^1)可以求,因为就是(3)嘛,其它的呢?其它的有哪些需要我们提前准备好呢?
有: (3^1),(3^2),(3^4),(3^8) ,注意,只有这几个啊,其它的(3^3),(3^5),(3^6),(3^7)可没有啊,不需要啊,因为有上面的这几个,就可以完美的组装出(13)了!
这些东东怎么求啊?这就简单了,就是每次翻一倍就是下一个了,比如 (3^4 = 3^2×3^2)
四、简单粗暴快速幂(无用版本)
此方法是我用来方便理解的,不可用于实际工作中,或者说,没有实用价值。因为一来系统中有现成的(pow(n,m)),另一个是不防溢出基本在数论题中无用。
#include <iostream>
using namespace std;
typedef long long LL;
int qmi(int a, int k) {
int res = 1;
while (k) {
if (k & 1) res = res * a;
k >>= 1;
a = (LL) a * a;
}
return res;
}
int main() {
cout<<qmi(3,4)<<endl;
return 0;
}
五、数论题目中的快速幂模板
#include <iostream>
using namespace std;
typedef long long LL;
int n;
// 快速幂 (a^k)%p
int qmi(int a, int k, int p) {
int res = 1; //答案
while (k) { //一路让k变小直到为0停止
if (k & 1) res = (LL) res * a % p; //如果k的个位是1的话
k >>= 1; //右移一位
a = (LL) a * a % p; //1-2-4-8-16,就是每进一位,是把a=a*a,注意使用long long 防止在乘积过程中爆了int
}
return res;
}
//快速幂
int main() {
scanf("%d", &n);
while (n--) {
int a, k, p;
scanf("%d%d%d", &a, &k, &p);
printf("%d
", qmi(a, k, p));
}
return 0;
}