杂题

题意

给定长度为(n)的序列(a_i)，(q)次询问，给定((l,r))，求(a_l^{a_{l+1}^{a_{l+2}^{cdots a_r}}})

做法

扩展欧拉定理

• (a^bequiv a^b(mod~p)(b<phi(p)))
• (a^bequiv a^{b\%phi(p)+phi(p)}(mod~p)(bge phi(p)))

(plongrightarrow phi(p)longrightarrow phi(phi(p)))，有效变化是(O(logp))的