思路
本题考察分治。
注意事项：
- 注意输出格式；
- 注意数据范围。
代码
核心代码：
long long pow(long long x,long long y){
if(y==1)return x;
if(y==0)return 1;
long long m=pow(x,y/2)%p,n;
n=(m%p*m%p)%p;
if(y%2>0){
n=(n%p*pow(x,y%2)%p)%p;
}
n%=p;
return n;
}
完整代码：
#include<bits/stdc++.h>
#define please return
#define AC 0
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
#define print cout<<
#define elif else if
#define cf(i) cout<<fixed<<setprecision(i)
using namespace std;
long long a,b,p,s=1;
long long pow(long long x,long long y){
if(y==1)return x;
if(y==0)return 1;
long long m=pow(x,y/2)%p,n;
n=(m%p*m%p)%p;
if(y%2>0){
n=(n%p*pow(x,y%2)%p)%p;
}
n%=p;
return n;
}
int main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
cin>>a>>b>>p;
s=pow(a,b);
s%=p;
printf("%lld^%lld mod %lld=%lld",a,b,p,s);
please AC;
}
暂无评论