Description
Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).
Input
There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.
Output
For each testcase, output an integer, denotes the result of A^B mod C.
Sample Input
3 2 42 10 1000
Sample Output
124
首先要降幂，由降幂公式：
（然而不知道公式是怎么来的。。。求指教）降幂后用快速幂计算
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll __int64
#define N 1000100
using namespace std;
char b[N];
ll p[N];
ll a, c;
ll quick(ll a, ll b){ //快速幂
ll k = 1;
while(b){
if(b%2==1){
k = k*a;
k %=c;
}
a = a*a%c;
b /=2;
}
return k;
}
void priem(){
memset(p, 0, sizeof(p));
ll i, j;
p[1] = 1;
for(i=2; i<=sqrt(N); i++){
for(j=2; j<=N/i; j++)
p[i*j] = 1;
}
}
ll ola(ll n){ //欧拉函数
ll i, j, r, aa;
r = n;
aa = n;
for(i=2; i<=sqrt(n); i++){
if(!p[i]){
if(aa%i==0){
r = r/i*(i-1);
while(aa%i==0)
aa /= i;
}
}
}
if(aa>1)
r = r/aa*(aa-1);
return r;
}
int main(){
ll d, i, j;
priem();
while(~scanf("%I64d%s%I64d",&a,b,&c)){
ll l = strlen(b);
ll B=0;
ll oc = ola(c);
// cout<<"oc = "<<oc<<endl;
for(i=0; i<l; i++){
B = B*10+b[i]-'0';
if(B>oc)
break;
}
//cout<<i<<endl;
if(i==l)
d = quick(a,B);
else{
B=0;
for(i=0; i<l; i++){ //降幂
B = (B*10+b[i]-'0')%oc;
}
d = quick(a,B+oc);
}
// printf("B= %I64d\n",B);
printf("%I64d\n",d);
}
return 0;
}版权声明：本文为wudi_00原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。