快速幂取余

快速幂取余

---

一、快速幂运算是什么，为什么用快速幂运算？

顾名思义，快速幂就是快速算底数的n次幂。在程序中如果计算a的b次幂，首先想到的可能是用for循环来一遍遍的遍历来求，会造成时间复杂度很大，在某些算法题造成超限等问题。

1.快速幂的解析（个人观点）

假设求 3 的 10 次方（3 ^10）
对于这个数 3^10 = 3^5 * 3^5;
而 3^5 = 3 * 3^2 * 3^2;
而 3^2 = 3 * 3；
所以用到二分的思想，来折半处理。

而对于取余的做法我们假设求（a * b) % c
可以化简为 (a % c) * (b % c) % c
而为什么 (a % c) * (b % c) 后面又要模上一个 c ？
原因是 (a % c) * (b % c) 的结果可能会进位，造成结果为大于 c 的数，所以还要模一个 c

二、两种幂运算的做法

1.for循环遍历做法

代码如下（示例）：

typedef long long int ll;
ll POW(ll a, ll b, ll c){
	ll ans = 1;
	for(ll i = 0; i < b; i++){
		ans *= a;
	}
	ans = ans % c;
	return ans;
}
1
2
3
4
5
6
7
8
9

关于for循环的时间复杂度为O(b），如果是a为10的9次方，第二次循环中的ans就为10的18次方，第三次则会更多，超出了long long的数据范围，程序会出现结果错误。

2.快速幂做法

(快速幂) ：

typedef long long int ll;
ll POW(ll a, ll b){
	ll ans = 1;
	while(b){
		if(b % 2 == 1){
			ans = ans * a;
		}
		a = a * a;
		b /= 2;
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12

（快速幂取余）：

typedef long long int ll;
ll POW(ll a, ll b, ll c){
	ll ans = 1;
	a = a % c;
	while(b){
		if(b % 2 == 1){
			ans = ans * a % c;
		}
		a = a * a % c;
		b /= 2;
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

关于快速幂运算可以减小数据的范围长度，并且时间复杂度缩减为O(logb)，极大的减少了运行的时间，提高程序的效率。