No.2592 Chubby Ghost 2
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
null