h832: 次方區間問題
Tags :
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-08 22:00

Content

給你一個正整數 $n$ 和一個正整數 $q$,代表有 $n$ 個數字$a_1, a_2, ..., a_n$和 $q$ 組詢問,每組詢問有一個區間 $[l, r]$ ,每次要你回答  $a_l^{{a_{l+1}}^{...^{a_r}}} \text{mod }m$

Input

第一行有兩個正整數 $n, m(1\le n\le 10^5, 1\le m\le 10^9)$,然後第二行有 $n$ 個數字 $a_1,a_2,...,a_n$其中$a_i(1\le a_i\le10^9,1\le i\le n)$ ,第三行有一個正整數 $q(1\le q\le 10^5)$ 表示有 $q$ 組詢問,接下來有 $q$ 行,每行有兩個正整數$l,r(1\le l\le r\le n)$代表詢問。

Output

輸出 $q$ 行,代表每個詢問的答案。

Sample Input #1
11 998244353
10 16 4 8 7 6 3 7 4 1 4
5
3 6
4 7
2 9
3 5
1 6
Sample Output #1
346033774
595427088
480750826
820873187
395868439
測資資訊:
記憶體限制: 256 MB
不公開 測資點#0 (10%): 2.0s , <1M
不公開 測資點#1 (10%): 2.0s , <1M
不公開 測資點#2 (10%): 2.0s , <1M
不公開 測資點#3 (10%): 2.0s , <1M
不公開 測資點#4 (10%): 2.0s , <1M
不公開 測資點#5 (10%): 2.0s , <10M
不公開 測資點#6 (10%): 2.0s , <1M
不公開 測資點#7 (10%): 2.0s , <10M
不公開 測資點#8 (10%): 2.0s , <10M
不公開 測資點#9 (10%): 2.0s , <1M
Hint :

$a^{b^c} = a^{(b^c)}$

$m$ 不一定是質數
$50\%$ 的測資 $n,q\le 1000$

$100\%$ 的測資 沒有特別限制

Tags:
出處:
[管理者:
Easonsfriend (becaidorz)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」