这题的话,用普通做法代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,p,ans;
int main()
{
cin >> a >> b >> p;
for(int i=1;i<=b;i++)
{
a*a;
ans=a*a;
}
cout << ans%p << endl;
return 0;
}
当然是不行的。。。
所以。。
用快速幂做
代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a,b,p,ans=0,k[107]={0},t=0;
long long md(int c)
{
if (c==0) return 1%p;
if (c==1) return a%p;
else {
long long x=md(c/2);
if(c%2==1)return x*x%p*a%p;
else return x*x%p;
}
}
int qim(int a,int b)
{
int res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
int main()
{
scanf("%d %d %d",&a,&b,&p);
ans = 1%p;
int tmp = a%p;
while (b!=0)
{
if(b%2==1){
ans = ans * tmp % p;
}
tmp = 1ll * tmp * tmp % p;
b=b/2;
}
printf("%d\n",ans);
return 0;
}