思路

利用乘方的性质：$a ^ p = a ^ {p / 2} * a ^ {p / 2}$ 来实现二分

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
int ksm(int a,int b,int c){
	if (b == 0)	return 1;
	int t = ksm(a,b / 2,c) % c;
	return (((t * t) % c) * (b & 1?a:1)) % c;
}
signed main(int argc, char **argv){
	cin >> a >> b >> c;
	printf("%lld^%lld mod %lld=%lld",a,b,c,ksm(a,b,c) % c);
	return 0; 
}

#include<iostream>
using namesbace std;
int main(){
    long long a,b,p,ans=1;
    cin>>a>>b>>p;
    cout<<a<<'^'<<b<<" mod "<<p<<'=';
    a%=p;
    while(b>0){
        if(b&1)ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    cout<<ans%p;
    return 0;
}

与A1326同理

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll binpow(ll a,ll b,ll k){
	ll res=1;
	while(b>0){
		if(b&1)res=res*a%k;
		a=a*a%k;
		b>>=1;
	}
	return res;
}
int main(){
	ll b,p,k;
	cin>>b>>p>>k;
	cout<<b<<'^'<<p<<' '<<"mod"<<' '<<k<<'='<<binpow(b,p,k);
	return 0;
}