今天常规,分享一个套路模板,快速求解快速幂问题。
题目:
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数,表示a^b mod p的值。
数据范围
0≤a,b,p≤10^9
数据保证 p≠0
输入样例:
3 2 7
输出样例:
2
数据范围位10^9,C++ 的O(n)级别算法支持10^7-10^8之间,所以需要比O(n)运算还快的logn算法。本题考察:快速幂。
实现方式分为递归与非递归。
思想
例如:5^10 = 5^2*5^8
。
5^10=5*5*5...*5
,总共9次计算。5^5=5*5*5*5*5
,总共5次计算。5*5^4
,5^4继续拆分为5^2*5^2
,5^2拆分为5*5
,总共4次计算。方式3的模拟过程,便是一个O(logn)的算法,也就是快速幂。递归法
上述方式3很快想到递归法解决。折半为奇,则a*f(a,b-1),为偶,则先保留一半的结果:f(a,b/2),再平方。
递归出口:幂为0,也就是b为0,此时直接返回1即可。
本题是对一个p进行前模,两个数相乘容易溢出,我们转long long类型,比较简单写法直接在第一个乘数后面乘上1ll。
int pow(int a,int b,int p) {
if(b==0) return 1%p;
else if(b%2==1) {
return pow(a,b-1,p)*1ll*a%p;
}
int temp = pow(a,b/2,p);
return temp*1ll*temp%p;
}
非递归法
我们把5的10次方写成,5^(1010)。上面1010为10的二进制表示。可以把它拆分为5^(1000) * 5^(10), 我们知道5^(1000...00)是5^1*5^2*5^4.....
。实现如下:
int pow(int a,int b,int p) {
int res = 1 % p;
while(b) {
if(b&1)
res = res*1ll*a %p; // res*a容易溢出,1ll转为long long类型
a = a * 1ll * a % p; // a^1 a^2... a^x
b >>= 1;
}
return res;
}