题意
求 $a^b\bmod p$ 。
分析
这题相当简单,可以说是个快速幂板子了。
快速幂的基本原理是把指数拆成二进制分解,例如 $6=4+2$ ,或者 $19=16+2+1$ 。由于 $a^(2^x)$ 可以倍增递推,因此复杂度可以保证。
注意有一个特殊的点中 $b=0,p=1$ ,要注意任意数对 $1$ 取模为 $0$ 。
代码
#include<bits/stdc++.h>
using namespace std;
int a,b,p;
#define ll long long
ll ksm(ll a,ll b,ll mod){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res%mod;
}
int main(){
scanf("%d%d%d",&a,&b,&p);
printf("%lld\n",ksm(a,b,p));
return 0;
}