题目描述
输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。
输入输出格式
输入格式:
三个整数b,p,k.
输出格式:
输出“b^p mod k=s”
s为运算结果
输入输出样例
输入样例#1:
2 10 9
输出样例#1:
2^10 mod 9=7 快速幂,随手取膜
#include<cstdio>
#include<iostream>
using namespace std;
int b,p,k;
#define LL long long LL q_pow(LL x,LL y)
{
LL ans=,base=x;
while(y!=)
{
if(y&)ans=(ans*base)%k;
base=(base*base)%k;
y>>=;
}
return ans;
}
int main()
{
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod "<<k<<"="<<q_pow(b,p)%k;
return ;
}