D. Power Tower

Codeforces

IDCF906D

Time4000ms

Memory256MB

Difficulty—

chinese remainder theoremmathnumber theory

English · Original

Chinese · Translation

Formal · Original

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 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_. ## Input First line of input contains two integers _n_ (1 ≤ _n_ ≤ 105) and _m_ (1 ≤ _m_ ≤ 109). Second line of input contains _n_ integers _w__k_ (1 ≤ _w__k_ ≤ 109) which is the power of rocks that priests have. Third line of input contains single integer _q_ (1 ≤ _q_ ≤ 105) which is amount of queries from priests to you. _k__th_ of next _q_ lines contains two integers _l__k_ and _r__k_ (1 ≤ _l__k_ ≤ _r__k_ ≤ _n_). ## Output Output _q_ integers. _k_\-th of them must be the amount of cumulative power the tower will have if is built from rocks _l__k_, _l__k_ + 1, ..., _r__k_. [samples] ## Note 327 = 7625597484987

基瓦尔科特神的祭司们希望建造一座塔，以象征他们神明的力量。塔通常由充满能量的岩石建造，通过一种稀有魔法构建：将当前塔顶悬浮，并在底部添加岩石。如果当前塔顶由 #cf_span[k - 1] 块岩石构成，其能量为 #cf_span[p]，现在要添加一块能量为 #cf_span[wk] 的岩石，则新塔的能量值为 #cf_span[{wk}p]。岩石的添加顺序是从最后一块到第一块。因此，对于序列 #cf_span[w1, ..., wm]，其能量值为塔建成后，其能量可能极大。但祭司们仍希望获取关于它的某些信息，具体来说，他们想知道一个称为“累积能量”的数值，即能量对 #cf_span[m] 取模后的真值。祭司们拥有 #cf_span[n] 块岩石，编号从 #cf_span[1] 到 #cf_span[n]。他们要求你计算：若使用编号为 #cf_span[l, l + 1, ..., r] 的岩石建造塔，塔将具有多少累积能量。输入的第一行包含两个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) 和 #cf_span[m] (#cf_span[1 ≤ m ≤ 109])。第二行包含 #cf_span[n] 个整数 #cf_span[wk] (#cf_span[1 ≤ wk ≤ 109])，表示祭司们拥有的岩石的能量值。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示祭司向你提出的查询次数。接下来的 #cf_span[q] 行中，第 #cf_span[k] 行包含两个整数 #cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ lk ≤ rk ≤ n])。请输出 #cf_span[q] 个整数。第 #cf_span[k] 个整数应为使用岩石 #cf_span[lk, lk + 1, ..., rk] 建造的塔的累积能量值。 #cf_span[327 = 7625597484987] ## Input 输入的第一行包含两个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) 和 #cf_span[m] (#cf_span[1 ≤ m ≤ 109])。第二行包含 #cf_span[n] 个整数 #cf_span[wk] (#cf_span[1 ≤ wk ≤ 109])，表示祭司们拥有的岩石的能量值。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示祭司向你提出的查询次数。第 #cf_span[k] 行包含两个整数 #cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ lk ≤ rk ≤ n])。 ## Output 请输出 #cf_span[q] 个整数。第 #cf_span[k] 个整数应为使用岩石 #cf_span[lk, lk + 1, ..., rk] 建造的塔的累积能量值。 [samples] ## Note #cf_span[327 = 7625597484987]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $, with $ 1 \leq n \leq 10^5 $, $ 1 \leq m \leq 10^9 $. Let $ W = (w_1, w_2, \dots, w_n) $ be a sequence of integers, where $ 1 \leq w_i \leq 10^9 $. For a subsequence $ W[l:r] = (w_l, w_{l+1}, \dots, w_r) $, define the **tower power** as the right-associative exponentiation: $$ P(l,r) = w_l^{w_{l+1}^{w_{l+2}^{\cdot^{\cdot^{\cdot^{w_r}}}}}} $$ **Constraints** 1. $ 1 \leq q \leq 10^5 $ 2. For each query $ k $, $ 1 \leq l_k \leq r_k \leq n $ **Objective** For each query $ (l_k, r_k) $, compute: $$ P(l_k, r_k) \bmod m $$ where exponentiation is evaluated **right-to-left** (top-down tower).

Samples

Input #1

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

Output #1

API Response (JSON)

{
  "problem": {
    "name": "D. Power Tower",
    "description": {
      "content": "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 curren",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF906D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 curren...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "基瓦尔科特神的祭司们希望建造一座塔，以象征他们神明的力量。塔通常由充满能量的岩石建造，通过一种稀有魔法构建：将当前塔顶悬浮，并在底部添加岩石。如果当前塔顶由 #cf_span[k - 1] 块岩石构成，其能量为 #cf_span[p]，现在要添加一块能量为 #cf_span[wk] 的岩石，则新塔的能量值为 #cf_span[{wk}p]。 \n\n岩石的添加顺序是从最后一块到第一块。因此，对于序列 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq m \\leq 10^9 $.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ be a sequence of integers, where $ 1 \\leq w_i \\leq 10^9 $.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments