快速幂算法

前言

算法都是因为需求而推出来的。

应用场景

有时会遇到 a^b%p （1<=a<=1e9,1<=b<=1e9,1<=p<=1e18）的题目

若要直接用pow算答案取余，直接变量越界。

若加以高精度优化，数组直接超空间

若循环b操作计数器，直接TLE

所以快速幂就被设计出来了。

主要思想

简单总结为 ： 2 ^ 4 = 4 ^ 2

有一个计数器ret=1；

每次对b操作

若b为奇数 ret * = a; ret % = p;
之后 b>>=1; a * = a; a % =p;

最终返回p;

总结

时间复杂度: O(log(b))

代码实现

#include
#define ll long long
using namespace std;

ll a,b,p,ans;
//快速幂
inline ll quick_sqrt(){
	ll ret=1;
	while(b){
		if(b&1)ret*=a,ret%=p;//b为奇数，处理
		b>>=1;
		a*=a;
		a%=p;
	}
	return ret;
}
int main(){
	scanf("%lld%lld%lld",&a,&b,&p);
	printf("%lld^%lld mod %lld=",a,b,p);
	ans=quick_sqrt();
	printf("%lld\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23