Super A^B mod C 快速幂+欧拉函数降幂

uper A^B mod C

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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 4

2 10 1000

Sample Output

首先要降幂，由降幂公式：

（然而不知道公式是怎么来的。。。求指教）

降幂后用快速幂计算

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #define ll __int64
 7 #define N 1000100
 8 using namespace std;
 9 char b[N];
10 ll p[N];
11 ll a, c;
12 ll quick(ll a, ll b){ //快速幂
13     ll k = 1;
14     while(b){
15         if(b%2==1){
16             k = k*a;
17             k %=c;
18         }
19         a = a*a%c;
20         b /=2;
21     }
22     return k;
23 }
24 void priem(){
25     memset(p, 0, sizeof(p));
26     ll i, j;
27     p[1] = 1;
28     for(i=2; i<=sqrt(N); i++){
29         for(j=2; j<=N/i; j++)
30             p[i*j] = 1;
31     }
32 }
33 ll ola(ll n){ //欧拉函数
34     ll i, j, r, aa;
35     r = n;
36     aa = n;
37     for(i=2; i<=sqrt(n); i++){
38         if(!p[i]){
39             if(aa%i==0){
40                 r = r/i*(i-1);
41                 while(aa%i==0)
42                     aa /= i;
43             }
44         }
45     }
46     if(aa>1)
47         r = r/aa*(aa-1);
48     return r;
49 }
50 int main(){
51     ll d, i, j;
52     priem();
53     while(~scanf("%I64d%s%I64d",&a,b,&c)){
54         ll l = strlen(b);
55         ll B=0;
56         ll oc = ola(c);
57       //  cout<<"oc = "<<oc<<endl;
58         for(i=0; i<l; i++){
59             B = B*10+b[i]-'0';
60             if(B>oc)
61                 break;
62         }
63         //cout<<i<<endl;
64         if(i==l)
65             d = quick(a,B);
66         else{
67             B=0;
68             for(i=0; i<l; i++){ //降幂
69                 B = (B*10+b[i]-'0')%oc;
70             }
71             d = quick(a,B+oc);
72         }
73       //  printf("B= %I64d
",B);
74         printf("%I64d
",d);
75     }
76     return 0;
77 }