$$\Large a_l^{a_{l+1}^{\dots^{a_r}}}$$

这么丑的式子怎么做啊。
首先这个指数看上去像一个子问题，但是子问题的模数要怎么取？
联想到扩欧。链接。

$$a^b \equiv \begin{cases} a^b \bmod \varphi(m), & \gcd(a, m) = 1, \\ a^b, & \gcd(a, m) \neq 1, b < \varphi(m), \pmod{m} \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, & \gcd(a, m) \neq 1, b \geq \varphi(m). \end{cases}$$

因此模数取 $\varphi(m)$。

有两个结论：

• $\forall m \gt 1,\varphi(m) \equiv 0 \pmod 2$。
  • 证明考虑辗转相除法，$\gcd(m,x) = \gcd(x,m-x) = 1$，所以互质情况总是成对出现的。
• $\forall m \equiv 0 \pmod 2 , \varphi(m) \leq \frac{m}{2}$。
  • 回归本质：$\varphi$ 的计算公式，由于含有 $2$ 质因子，所以至少有一项为 $\frac{1}{2}$。

因此子问题递归最多 $O(\log m)$ 层模数就会变为 $1$。

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

const int N = 1e6 + 5;
int n, p, w[N], q;
unordered_map<int, int> mp;

int phi(int x) {
    if (mp[x]) return mp[x];
    int res = x;
    for (int i = 2; i <= x / i; i++) {
        if (x % i) continue;
        res = res / i * (i - 1);
        while (x % i == 0) x /= i;
    }
    if (x > 1) res = res / x * (x - 1);
    return mp[x] = res;
}

int chk(long long x, int mod) { return (x < mod) ? x : (x % mod + mod); }

int qmi(int a, int k, int mod) {
    int res = 1 % mod;
    while (k) {
        if (k & 1) res = chk(res * 1ll * a, mod);
        a = chk(a * 1ll * a, mod), k >>= 1;
    }
    return res;
}

int dfs(int l, int r, int mod) {
    if (l == r || mod == 1) return chk(w[l], mod);
    return qmi(w[l], dfs(l + 1, r, phi(mod)), mod);
}

int main() {
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    scanf("%d", &q);
    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", dfs(l, r, p) % p);
    }
    return 0;
}