P3934题炸脖龙I，如何巧妙解决？

P3934 [Ynoi Easy Round 2016] 炸脖龙 I 大意 区间加，求 \(a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p\) 的值。 思路 对于这个指数塔，非常逆天，我们首先想到的肯定的是与降幂有关的内容，也就只有欧拉定理了，由于 \(p\) 并非是质数，我们需要用扩展欧拉定理，那么什么是欧拉定理和扩展欧拉呢？ \(\varphi(n)\) 就表示小于等于 \(n\) 与 \(n\) 互质的数的个数，\(\varphi(1) = 1, \varphi(p) = p - 1\)，这里的 \(p\) 是质数。那么 \(\phi(n)\) 应该怎么算呢？我们由素数分解定理，就可以有这样的公式： \[n \prod_{p | n} (1 - \frac{1}{p}) \] 这个过程我们是可以用线性筛预处理这个 \(\varphi(n)\) 的。 好的，预处理讲完了，接下来讲欧拉定理，当 \(\gcd(a, m) = 1\)，那么 \(a ^ {\varphi(m)} \equiv 1 \pmod m\)，这个在模数为质数的时候就可以快速降幂，但是要是不是质数呢？没事，我们有扩展欧拉定理，其内容如下： \[a ^ b \equiv \begin{cases} a ^ {b \pmod{\varphi(m)}} & \gcd(a, m) = 1 \\ a ^ b & \gcd(a, m) \neq 1, b < \varphi(m) \\ a ^ {b \pmod{\varphi(m)} + \varphi(m)} & \gcd(a, m) \neq 1, b \ge \varphi(m) \end{cases} \pmod{m} \] 好了，知道了这些，我们回到这个题目，对于这个指数塔，其指数一直取 \(\varphi\) 显然最后会变成 \(1\)，那么要取多少次呢？我们想想对于 \(\varphi(2 ^ k)\) 来说，其等于 \(2 ^ {k - 1}\)，对于质数是 \(p - 1\)，其如果是质数就减去一变成偶数，然后就会很快变小。 那么我们这个题直接写递归的话，递归层数最多就是 \(\log\) 的层级，我们为了维护区间加和单点查询，我们直接用个树状数组维护即可，在递归的过程中，不断判断模数是否为 \(1\)，注意快速幂的地方，也要改一下。