問題一覧 > 通常問題

No.2592 Chubby Ghost 2

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 39
作問者 : null / テスター : nu50218
お気に入りにしたユーザー ProblemId : 8238 / 自分の提出
問題文最終更新日: 2023-12-19 21:29:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2023 (順位表) の他の問題:

Debu

This problem is also featured in でぶ Advent Calendar 2023.

Problem Statement

Obake-san, a ghost living in the shojin Kingdom, is making a meal plan, being careful not to become fat.

The shojin Kingdom has $n$ shops, each of which is a restaurant or a training gym. The $i$-th shop is a restaurant that serves only food of $a_i$ calories per meal if $0 \le a_i$, and a training gym offering an exercise that burns $|a_i|$ calories per session if $a_i < 0$. The $i$-th shop is called shop $i$.

Obake-san's meal plan consists of a tuple of positive integers $(l, r, x)$. In the meal plan, Obake-san visits shop $i$ in the order $i = l, l+1, \dots, r-1, r$. At shop $l$, Obake-san eats or exercises $1$ time. However, Obake-san's appetite grows with every shop visited, and more exercise becomes necessary accordingly, so Obake-san eats or exercises $x$ times the amount done at the previous shop. More precisely, at shop $i$, Obake-san eats food or exercises $x^{i-l}$ times.

From the above, Obake-san's final calorie intake is expressed by the following formula. $$\sum_{i=l}^{r} a_i x^{i-l}$$

However, Obake-san becomes fat if and only if the final calorie intake is a multiple of $x-k$. Here, an integer $A$ is said to be a multiple of $x-k$ if there exists an integer $B$ such that $A=(x-k)B$.

You are given $q$ queries. In each query, $l, r$ are given; determine whether there exists an $x$ such that Obake-san does not become fat.

Constraints

  • $1 \le n, q \le 10^5$
  • $2 \le k \le 10^{18}$
  • $-10^{18} \le a_i \le 10^{18}$
  • $1 \le l_i \le r_i \le n$
  • All inputs are integers.

Input

$n\ q\ k$
$a_1\ a_2\ \dots\ a_n$
$l_1\ r_1$
$l_2\ r_2$
$\vdots$
$l_q\ r_q$

Output

For each query, print Yes if an $x$ satisfying the condition exists, and No if it does not. Print a newline at the end.

Sample

Sample 1
Input
6 5 2
-4 -4 1 1 -2 1
1 1
1 4
5 6
6 6
1 6
Output
Yes
No
No
Yes
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。