题解 P5091 [模板]欧拉定理

发表于 | 分类于 | 阅读次数：

题面
扩展欧拉定理

用快读读入即可

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
#include <bits/stdc++.h>
using namespace std;
int a, p, b, phi = 1, tmp;
inline int read() {
    int c, a = 0, f = 0;
    for(c = getchar(); !isdigit(c); c = getchar());
    for(; isdigit(c); c = getchar()) {
        a = a * 10 + c - 48;
        if(a >= phi) f = 1;
        a %= phi;
    }
    return a + f * phi;
}
inline int power(int a, int b, int p) {
    // printf("%d\n", b);
    long long res = a, ans = 1;
    for(; b; b >>= 1, res = res * res % p) if(b & 1) ans = ans * res % p;
    return ans;
}
int main() {
    scanf("%d%d", &a, &p);
    tmp = p;
    for(int i = 2; i * i <= tmp; i++) {
        if(tmp % i == 0) {
            tmp /= i;
            phi *= i - 1;
            while(tmp % i == 0) tmp /= i, phi *= i;
        }
    }
    if(tmp > 1) phi *= tmp - 1;
    return printf("%d\n", power(a, read(), p)), 0;
}