题解 | #Power Tower#

【Power Tower】

$m\to \phi (m)\to \phi (\phi (m))\to \mathrm{.}\mathrm{.}\mathrm{.}\to 1m\backslash rightarrow\; \backslash varphi(m)\; \backslash rightarrow\; \backslash varphi(\backslash varphi(m))\; \backslash rightarrow...\backslash rightarrow1$ ，这个步骤最多会进行$\log m\backslash log\; m$次。

对于每次的查询区间$[l,r][l,r]$，最多计算$\log m\backslash log\; m$次，总的复杂度就是$O(q\log m)O(q\backslash log\; m)$。

计算幂的时候要用到欧拉降幂。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

int n, m, w[N], q;
int phi_m[N], total;
bool k;

int power(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
            if (res >= mod) {
                k = true;
                res %= mod;
            }
        }
        a = a * a;
        if (a >= mod) {
            k = true;
            a %= mod;
        }
        b >>= 1;
    }
    return res;
}

int f(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

void init() {
    int tmp = m;
    total = 0;
    phi_m[++total] = tmp;
    while (tmp != 1) {
        tmp = f(tmp);
        phi_m[++total] = tmp;
    }
}

void solve(int l, int r) {
    r = min(r, l - 1 + total);
    int res = 1;
    for (int i = r; i >= l; i--) {
        k = false;
        res = power(w[i], res, phi_m[i - l + 1]);
        if (k) res += phi_m[i - l + 1];
    }
    cout << res % phi_m[1] << "\n";
}

signed main() {
    cin >> n >> m;
    init();  // 预处理欧拉函数的值
    for (int i = 1; i <= n; i++) cin >> w[i];
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        solve(l, r);
    }
    return 0;
}