对于快速幂有以下性质:
-
(a + b) % p = (a % p + b % p) % p (1)
-
(a - b) % p = (a % p - b % p ) % p (2)
-
(a * b) % p = (a % p * b % p) % p (3)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,p;
ll mi(ll a,ll b,ll p){
//这题要用long long 不然会有错误,超出int类型存储的极限
if (b == 0) return 1%p;
ll ans = 1;
while(b > 0){
if(b & 1) //即 b % 2 != 0
ans = ans *a % p;
b >>= 1;
a = a * a % p;
}
return ans;
}
int main(){
cin>>a>>b>>p;
cout<<mi(a,b,p)<<endl;
return 0;
}
参考: https://blog.csdn.net/qq_19782019/article/details/85621386