题意

让你求

思路

假设要求，

根据拓展欧拉定理，我们可以得到 ,

接着继续求，还是根据拓展欧拉定理可以得到

当然上面的情况都是建立指数大于 的情况， 对于指数小于 的情况，我们就是直接返回不加的版本，那么这个判断也太复杂了！

偷学了个小技巧，我们可以修改取模的这个操作，的情况我们就返回 ，不然就返回 ，这样的话，我们就能保证结果的正确性

代码

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

#define dd(x) cout << #x << " = " << x << ' '
#define de(x) cout << #x << " = " << x << '\n'

int Mod(ll a, ll b) { return a > b ? a % b + b : a; }

int get_phi(int x) {
    int ret = 1;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            ret *= (i - 1);
            x /= i;
            while(x % i == 0) {
                ret *= i;
                x /= i;
            }
        }
    }
    if (x != 1) ret *= (x - 1);
    return ret;
}

int kpow(int a, int b, int c) {
    int ret = 1;
    while(b) {
        if (b & 1) {
            ret = Mod(1ll * ret * a, c);
        }
        a = Mod(1ll * a * a, c);
        b >>= 1;
    }
    return ret;
}

int gao(int l, int r, int i, const vector<int>& w, const vector<int>& p) {
    // dd(l), de(r);
    if (l >= r || p[i] == 1) return Mod(w[l], p[i]);
    return kpow(w[l], gao(l + 1, r, i + 1, w, p), p[i]);
}

int main() {
    int n, m; cin >> n >> m;
    vector<int> w(n);
    for (int i = 0; i < n; ++i) cin >> w[i];
    int q; cin >> q;
    vector<int> p;
    p.push_back(m);
    // de(0);
    while(p.back() != 1) p.push_back(get_phi(p.back()));
    // de(1);
    // for (int i = 0; i < p.size(); ++i) dd(i), de(p[i]);
    while(q--) {
        int l, r; cin >> l >> r;
        // dd(l), de(r);
        l--; r--;
        cout << gao(l, r, 0, w, p) % m << '\n';
    }
    return 0;
}