AcWing 思维. 64位A*64位B
原题链接
简单
作者:
笨小孩与坏童鞋
,
2022-05-01 22:01:25
,
所有人可见
,
阅读 139
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int INF=1e9+5;
const int maxn=3e7+10;
const ll MOD=998244353;
/*
总体思路:因为太大,所以我们要把他拆掉。但怎么拆才能让他复杂度不高?----分块思想。logn的快速幂
5*7=5*(1+6) =5+5*6;
其中 5放入ans中。
5*6可以拆成5*3*2=10*3;以此类推。
最终应该是:5+[5*6]=5+[10*3]=5+[10+[10*2]]=5+[10+[20*1]] =5+[10+[20]]=35;
这么写的原因就是ksm是logn的级别。 1e18也才60次;
1e9=30次。
变小又不会超时
*/
ll p;
ll ksm(ll a,ll k){
ll ans=0;
while(k)
{
if(k&1) ans=(ans+a)%p;
a=(a+a)%p;
k>>=1;
}
return ans;
}
ll a,b;
int main(){
cin>>a>>b>>p;
cout<<ksm(a,b)<<endl;
return 0;
}