快速幂取模

首先得知道余数有如下性质：

1. (a+b)％m == (a％m+b％m)％m
2. a*b%c=((a%c)*b)%c
3. ab%c=(a%c)*b%c
4. a^p=aa…*a=(a%p) *(a%p) * … *(a%p)
   代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL  quickMod(LL a, LL p, LL mod) {
	p%=mod;
    LL base=1;
    while(p) {
        if(p&1) base=base*a%mod;
        a=a*a%mod; 
		p>>=1;
    }
    return base;
}
int main(){
	int a,p,mod;
	scanf("%d%d%d",&a,&p,&mod); 
	printf("%d\n",quickMod(a,p,mod));
}