我们都知道快速幂能算一个数的高次幂,那么如果a,n,mod 都是1e18级别的呢?
可知无论在快速幂中怎么模都会爆long long,所以我们需要一种不会爆ll的乘法——快速乘
快速乘非常好写,只需将快速幂稍作改动即可
ll quick_multi(ll a,ll n,ll mod) { ll ans = 0;//这里一定记得初始化为0 while(n) { if(n & 1) ans = (ans+a) % mod; a = (a+a) %mod; n >>= 1; } return ans; } ll quick_pow(ll a,ll n,ll mod) { ll ans = 1; while(n) { if(n & 1) ans = quick_multi(ans,a,mod); a = quick_multi(a,a,mod); n >>= 1; } return ans; } int main(int argc, char const *argv[]) { int t; scanf("%d",&t); while(t--) { ll A,B,P; scanf("%lld%lld%lld",&A,&B,&P); printf("%lld\n",quick_pow(A,B,P)); } return 0; }