5208 求乘方取模
时间限制: 1 s
空间限制: 1000 KB
题目等级 : 未定级
题目描述 Description
给定非负整数A、B、M，求(A ^ B) mod M。
输入描述 Input Description
包含多组输入，输入处理到EOF。
每组输入仅一行，三个用空格隔开的非负整数A、B、M。
输出描述 Output Description
对于每组输入，输出一行，一个非负整数，即(A ^ B) mod M。
样例输入 Sample Input
2 3 100006
32 71 83
900 800 777
样例输出 Sample Output
8
5
219
数据范围及提示 Data Size & Hint
0 <= A, B < 8 * 10^18。
0 < M < 8 * 10^18。
保证A和B不同时为0。
/*
快速幂.
快速乘法防爆.
*/
#include<iostream>
#include<cstdio>
#define LL unsigned long long
using namespace std;
LL a,b,k;
LL Mul(LL a,LL b,LL c)
{
LL ans=0;
while(b)
{
if(b&1)
{
b--;ans+=a;ans%=c;
}
b>>=1;a<<=1;a%=c;
}
return ans;
}
LL fast_mi(LL a,LL b,LL k){
LL tot=1;
while(b){
if(b&1) tot=Mul(tot,a,k);
a=Mul(a,a,k);
b>>=1;
}
return tot;
}
int main()
{
while(cin>>a>>b>>k){
if(!a)printf("0\n");
else if(!b) {
cout<<1%k;printf("\n");
}
else {
cout<<fast_mi(a,b,k);
printf("\n");
}
}
return 0;
}