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

题目

http://acm.fzu.edu.cn/problem.php?pid=1759

题意

给定A,B和C的值,求$A^{B}modC的值,其中1<=A,C<=1e10,1<=B<=10e1000000

分析

今天刚刚学到一个内容,指数降幂公式,即$A^{B}modC=A^{Bmodphi(c)+phi(c)}modC$

用这个公式,可以很方便地对大指数问题进行降维处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 1000005;
typedef long long ll;
char str[maxn];
int phi(int n){
int res = n;
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
res = res - res / i;
while(n % i == 0) n /= i;
}
}
if(n > 1)
res = res - res / n;
return res;
}
ll multi(ll a, ll b, ll m){
ll ans = 0;
a %= m;
while(b){
if(b & 1){
ans = (ans + a) % m;
b--;
}
b >>= 1;
a = (a + a) % m;
}
return ans;
}
ll quickmod(ll a, ll b, ll m){
ll ans = 1;
a %= m;
while(b){
if(b & 1){
ans = multi(ans, a, m);
b--;
}
b >>= 1;
a = multi(a,a,m);
}
return ans;
}
int main(){
ll a,c;
while(~scanf("%I64d%s%I64d", &a, str, &c)){
ll len = strlen(str);
ll ans = 0;
ll p = phi(c);
if(len <= 15){
for(int i = 0 ; i < len; i++)
ans = ans * 10 + str[i] - '0';
}else{ // A^B%C = A^(B%phi(C)+phi(C))%C
for(int i = 0 ; i < len ; i++){
ans = ans * 10 + str[i] - '0';
ans %= p;
}
ans += p;
}
printf("%I64d\n", quickmod(a,ans,c));
}
}