Super A^B mod C （快速幂+欧拉函数+欧拉定理）

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1759

题目：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

思路：由于B的数据太大，因而我们需要借助欧拉定理来进行降幂，然后再用快速幂解决。

代码实现如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int maxn = 1e6 + 7;
 5 long long a, b, c;
 6 char s[maxn];
 7 
 8 int euler(int x) {
 9     int ans = x;
10     for(int i = 2; i * i <= x; i++) {
11         if(x % i == 0) {
12             ans = ans / i * (i - 1);
13             while(x % i == 0) x /= i;
14         }
15     }
16     if(x > 1) ans = ans / x * (x - 1);
17     return ans;
18 }
19 
20 long long ModPow(int n, int p, int mod) {
21     long long rec = 1;
22     while(p) {
23         if(p & 1) rec = rec * n % mod;
24         n = (long long) n * n % mod;
25         p >>= 1;
26     }
27     return rec;
28 }
29 
30 int main() {
31     while(~scanf("%lld%s%lld", &a, s, &c)) {
32         b = 0;
33         int rec = euler(c);
34         int len = strlen(s);
35         for(int i = 0; i < len; i++) {
36             b = b % rec;
37             b = ((s[i] - '0') + 10 * b) % rec;
38         }
39         b += rec;
40         printf("%lld
", ModPow(a, b, c));
41     }
42     return 0;
43 }

Super A^B mod C （快速幂+欧拉函数+欧拉定理）

Input

Output

Sample Input

Sample Output

相关推荐