本文共 1945 字，大约阅读时间需要 6 分钟。

题意：

给一个序列，q个询问，每个询问回答  区间的幂塔 % m

思路：

由扩展欧拉定理：（图源

重定义取模运算，对每个询问递归求解，记忆化欧拉函数的值

#include 
   
    using namespace std;typedef long long ll;#define MOD(a, b) a < b ? a : a % b + bconst ll inf = 0x3f3f3f3f3f3f3f3f;const ll N = 1e6 + 10;ll w[N], p, q, n, l, r, pri[N];map
    
     eul;ll qpow(ll a, ll b, ll p) {    ll ans = 1;    a = MOD(a, p);    while(b) {        if(b & 1) ans = MOD(ans * a, p);        a = MOD(a * a, p);        b >>= 1;    }    return MOD(ans, p);}void init() {    eul.clear();    memset(pri, 0, sizeof(pri));    for(ll i = 2; i < N; ++i) {        if(!pri[i]) pri[++pri[0]] = i;        for(ll j = 1; j <= pri[0] && pri[j] < N / i; ++j) {            pri[pri[j] * i] = 1;            if(i % pri[j] == 0) break;        }    }}ll factor[N][2];ll fatCnt;void getFactors(ll x) {    fatCnt = 0;    ll tmp = x;    for(ll i = 1; pri[i] <= tmp / pri[i]; ++i) {        factor[fatCnt][1] = 0;        if(tmp % pri[i] == 0) {            factor[fatCnt][0] = pri[i];            while(tmp % pri[i] == 0) {                factor[fatCnt][1]++;                tmp /= pri[i];            }            fatCnt++;        }    }    if(tmp != 1) {        factor[fatCnt][0] = tmp;        factor[fatCnt++][1] = 1;    }}ll euler(ll n) {    if(eul[n]) return eul[n];    getFactors(n);    ll ret = n;    for(ll i = 0; i < fatCnt; ++i)        ret = ret / factor[i][0] * (factor[i][0] - 1);    eul[n] = ret;    return ret;}ll solve(ll l, ll r, ll mod)    if(l == r || mod == 1) {        return MOD(w[r], mod);    return qpow(w[l], solve(l + 1, r, euler(mod)), mod);}int main() {    init();    scanf("%lld%lld", &n, &p);    for(ll i = 1; i <= n; ++i) scanf("%lld", &w[i]);    scanf("%lld", &q);    for(ll i = 1; i <= q; ++i) {        scanf("%lld%lld", &l, &r);        printf("%lld\n", solve(l, r, p) % p);    }	return 0;}/*10 20792708224 4633945 600798790 384332600 283309209 762285205 750900274 160512987 390669628 205259431105 910 108 107 107 1010 104 410 107 74 8*/