版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [CodeForces 906 D] Power Tower" categories:
time limit per test: 4.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from $k-1$ rocks, possesses power $p$ and we want to add the rock charged with power $w_k$ then value of power of a new tower will be ${w_k}^p$
Rocks are added from the last to the first. That is for sequence $w_1, ..., w_m$ value of power will be
$$ w_1^{w_2^{\cdot^{\cdot^{\cdot^{w_m}}}}} $$
After tower is built, its power may be extremely large. But still priests want to get some information about it, namely they want to know a number called cumulative power which is the true value of power taken modulo $m$. Priests have $n$ rocks numbered from $1$ to $n$. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered $l, l + 1, ..., r$
First line of input contains two integers $n$ ($1 ≤ n ≤ 10^5$) and $m$ ($1 ≤ m ≤ 10^9$)
Second line of input contains $n$ integers $w_k$ ($1 ≤ w_k ≤ 10^9$) which is the power of rocks that priests have
Third line of input contains single integer $q$ ($1 ≤ q ≤ 10^5$) which is amount of queries from priests to you
kth of next $q$ lines contains two integers $l_k$ and $r_k$ ($1 ≤ l_k ≤ r_k ≤ n$)
Output $q$ integers. k-th of them must be the amount of cumulative power the tower will have if is built from rocks $lk, l{k + 1}, ..., r_k$
6 1000000000
1 2 2 3 3 3
8
1 1
1 6
2 2
2 3
2 4
4 4
4 5
4 6
1
1
2
4
256
3
27
597484987
$3^{27} = 7625597484987$
给出 $n,m,w_1,w_2,\dots,w_n$, 有 $q$ 组询问, 每次给出 $l,r$, 问
$$ wl^{w{l+1}^{\cdot^{\cdot^{\cdot^{w_r}}}}}\bmod m $$
由扩展 Euler 定理
$$ a^b\equiv\begin{cases} a^{b\bmod\varphi(m)+\varphi(m)},&(a,m)>1,b>\varphi(m)\ a^{b\bmod\varphi(m)},&\texttt{otherwise}\ \end{cases}\pmod m $$
递归求解即可
$$ \Theta\left(\log m+\sum_{i=1}^q\min{r_i-l_i+1,\log m}\right)\implies O(q\log m) $$