NO IMAGE

qpow 快速冪

 

#include <iostream>
using namespace std;
typedef long long ll;
ll N, M, MOD;
ll qpow(ll a, ll b)
{
ll ans = 1;
while(b) 
{
if(b&1) //按位異或
ans = ( ans * a ) % MOD;
a = (a * a) % MOD;
b >>= 1; //去位
}
return ans % MOD;
}
int main()
{
cin>>N>>M>>MOD;
ll ans = qpow(N, M);
cout<<N<<'^'<<M<<" mod "<<MOD<<'='<<ans<<endl;
return 0;
}