题解 p5091 [模板]欧拉定理

using namespace std;
int a, p, b, phi = 1, tmp;
inline int () {
    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) {
    
    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("%dn", power(a, read(), p)), 0;
}