fzu 1759Super A^B mod C 指数循环节

Problem 1759 Super A^B mod C

Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem 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 24

Source

FZU 2009 Summer Training IV--Number Theory

欧拉定理的推广——有关的高次幂取模（指数循环节）

公式： a^x mod(c)=a^{(x mod phi(c) +phi(c))} mod(c)， (x>=phi(c))

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long int ll;
 6 
 7 const int MAXN = 1e6;
 8 int prime[MAXN+10], cnt = 0;
 9 int a[MAXN+10];
10 
11 ll pow_mod(ll a, ll n, ll mod){
12     ll ans = 1;
13     while(n > 0){
14         if(n&1) {
15             n--;
16             ans = ans*a%mod;
17         }
18         n >>= 1;
19         a = a*a %mod;
20     }
21     return ans;
22 }
23 
24 void init(){
25     for(int i = 2; i <= MAXN; i++) a[i] = true;
26     for(int i = 2; i <= MAXN; i++){
27         if(a[i]){
28             prime[++cnt] = i;
29         }
30         for(int j = 1; j <= cnt; j++){
31             if(prime[j]*i > MAXN) break;
32             a[prime[j]*i] = false;
33             if(i%prime[j] == 0) break;
34         }
35     }
36 }
37 ll Euler(ll n){
38     ll ans = n;
39     for(int i = 1; i <= cnt && prime[i] <= n; i++){
40         if(n%prime[i] == 0){
41             while(n%prime[i] == 0){
42                 n /= prime[i];
43             }
44             ans = ans/prime[i]*(prime[i]-1);
45         }
46     }
47     return ans;
48 }
49 ll slove(ll a, char s[], ll c, ll mod){
50     ll sum = 0;
51     int len = strlen(s);
52     sum = (s[0] - '0') %mod;
53     for(int i = 1; i < len; i++){
54         sum *= 10;
55         sum = (sum + s[i] - '0')%mod;
56     }
57    // printf("sum = %I64d
", sum);
58     return pow_mod(a, mod+sum, c);
59 }
60 int main(){
61     ll a, c;
62     char b[MAXN+10];
63     init();
64     while(scanf("%I64d%s%I64d", &a, b, &c) != EOF){
65         ll p = Euler(c);
66        // printf("p = %I64d
", p);
67         printf("%I64d
", slove(a, b, c, p));
68     }
69 
70 }