#include <bits/stdc++.h>
#define int long long
using namespace std;
int power[105];
int ans=1;
signed main(){
	int a,b,p;
	cin>>a>>b>>p; 
	int nb=b;
	power[0]=a;
	for(int i=1;pow(2,i)<=b;i++){
		power[i]=(power[i-1]*power[i-1])%p;
	}
	while(b>0){
		int zs=0;
		while(pow(2,zs)<=b){
			zs++;
		}
		zs--;
		b-=pow(2,zs);
		ans*=power[zs];
		ans%=p;
	}
	cout<<a<<"^"<<nb<<" mod "<<p<<"="<<ans;
	return 0;
}

倍增做法

$f[i]$代表$a^{2^i}$。

#include<bits/stdc++.h>
using namespace std;
long long f[31];
int main(){
	int a,b,p;
	cin>>a>>b>>p;
	int tb=b;
	f[0]=a;
	for(int i=1;i<31;i++)f[i]=f[i-1]*f[i-1]%p;
	long long ans=1;
	for(int i=30;i>=0;i--){
		if((1<<i)<=b){
			b-=1<<i;
			ans*=f[i];
			ans%=p;
		}
	}
	cout<<a<<"^"<<tb<<" mod "<<p<<"="<<ans;
}