题目大意

给出 $a$, $b$, $p$。求 $a^b\bmod p$。

做法

注意到 $b\leq 2^{31}$ ,所以我们最好可以有一个$\mathit{O(logn)}$的算法来求快速幂。那么，分治，它来了。

详细介绍

接下来，就是思考如何用分治解决这个题目。当我们求 $a^b\bmod p$ 时，我们可以把原式子分为两个 $a^{b/2}\bmod p$ 的积, 如果 $b\equiv1\pmod{2}$ ,还得乘上一个 $a$ 才能等于 $a^b\bmod p$ 。这样递归下去，我们就能实现分而治之了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int x,y,p;
int pw(int x,int y,int p){
	int re=1;
	while(y){
		if(y&1) re=re*x%p;//y&1是判y的奇偶性
		x=x*x%p;
		y>>=1;//等同于y/=2
	}
	return re;
} 
signed main(){
	cin>>x>>y>>p;
	cout<<pw(x,y,p)<<endl;
	return 0;
}

完结，撒花！！！