# T5 数据结构题 题解

我们将询问转化为如下问题

定义 $f(l,r)$ $(l \le r)$ 如下：

当 $l=r$ 时，$f(l,r)=a_l$；否则，$f(l,r)=a_l^{f(l+1,r)}$

每次操作 $2$，输出 $f(l,r)\bmod p$

那我们该如何维护呢？

这里我们需要一个前置知识，叫做扩展欧拉定理，即：

$$a^b\equiv \begin{cases}a^{b \bmod \varphi(p)}(b<\varphi(p))\\a^{b \bmod \varphi(p)+\varphi(p)}(b\ge\varphi(p))\end{cases}\pmod p$$

那么

$$f(l,r)\equiv a^{f(l+1,r)\bmod \varphi(p)+[b\ge \varphi(p)]\times \varphi(p)}\pmod p$$

那么，求解 $f(l,r)\bmod p$ 就变成了求解 $f(l+1,r)\bmod \varphi(p)$，并判断 $f(l+1,r)$ 与 $p$ 的关系

然后我们就可以递归求解了

递归边界的话，则有三个

当 $l=r$ 时，$f(l,r)\bmod p\equiv a_l\pmod p$

当 $p=1$ 时，$f(l,r)\bmod p\equiv 0\pmod p$

当 $a_l=1$ 时，$f(l,r)\bmod p\equiv 1\pmod p$

那么这个递归的复杂度是多少呢？

我们分析一下将 $\varphi(p)\to p$ 直到 $p=1$ 的时间复杂度是多少

由 $\varphi(p)=p\prod_{i=1}^{n} \frac{p_i-1}{p_i}$ $(p=\prod_{i=1}^{n}{p_i}^{k_i})$可知

当 $p$ 为偶数时，上述式子必有一项是 $\frac{1}{2}$，所以 $\varphi(p)\le\frac{1}{2}p$

当 $p$ 为奇数时，上述式子的 $p_i-1$ 必是偶数，因此 $\varphi(p)$ 为偶数，回到 $p$ 为偶数的情况

因此最多经过 $O(logn)$ 次递归就可以得出答案

至于判断 $f(l+1,r)$ 与 $p$ 的关系，可以让递归函数返回一个结构体，结构体第一项存 $f(l+1,r)\bmod \varphi(p)$ 的值，第二项存 $f(l+1,r)$ 与 $\varphi(p)$ 的大小关系，前者大于等于后者，这一项就是 $1$，反之则为 $0$

区间和我们用树状数组维护差分即可

时间复杂度：$O(mlogqlogn)$