The Preliminary Contest for ICPC Asia Nanjing 2019

B. super_log

https://nanti.jisuanke.com/t/41299

很容易推出来是一个连续的幂次。这里主要是要知道扩展欧拉定理对互质肯定也是生效的，不需要整这么多东西。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int qpow2(ll x, int n, int m) {
    int _2m = m + m;
    ll res = 1;
    while(n) {
        if(n & 1) {
            res = res * x;
            if(res >= _2m)
                res = (res % m) + m;
        }
        x = x * x;
        if(x >= _2m)
            x = (x % m) + m;
        n >>= 1;
    }
    return res;
}

bool np[1000005];
int phi[1000005];
int pri[800005];
int ptop;

void sieve(int n) {
    np[1] = 1;
    phi[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!np[i]) {
            pri[++ptop] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= ptop; ++j) {
            int t = i * pri[j];
            if(t > n)
                break;
            np[t] = 1;
            if(!(i % pri[j])) {
                phi[t] = phi[i] * pri[j];
                break;
            } else
                phi[t] = phi[i] * (pri[j] - 1);
        }
    }
}

int solve(int a, int b, int m) {
    if(m == 1 || b == 0)
        return 1;
    else
        return qpow2(a, solve(a, b - 1, phi[m]), m);
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    sieve(1000000);
    int T;
    scanf("%d", &T);
    while(T--) {
        int a, b, m;
        scanf("%d%d%d", &a, &b, &m);
        printf("%d\n", solve(a, b, m) % m);
    }
}

The Preliminary Contest for ICPC Asia Nanjing 2019

原文：https://www.cnblogs.com/Inko/p/11443290.html