/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の数列 A が与えられるので、以下の Q 個の質問に答えてください。
- i 個目の質問では整数 L_i,R_i が与えられます。 A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i} は立方数ですか?
ただし、ある正整数 x が立方数であるとは、 x=y^3 を満たすある正整数 y が存在することを言います。
制約
- 入力は全て整数
- 1 \le N,Q \le 2 \times 10^5
- 1 \le A_i \le 10^6
- 1 \le L_i \le R_i \le N
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \dots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
Q 行出力せよ。
i 行目には、i 個目の質問について A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i} が立方数なら Yes 、そうでないなら No と出力せよ。
なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。
入力例 1
8 5 7 49 30 1 15 8 6 10 1 2 2 3 4 4 5 8 3 8
出力例 1
Yes No Yes No Yes
- 1 個目の質問について、 7 \times 49 = 343 は立方数です。
- 2 個目の質問について、 49 \times 30 = 1470 は立方数ではありません。
- 3 個目の質問について、 1 は立方数です。
- 4 個目の質問について、 15 \times 8 \times 6 \times 10 = 7200 は立方数ではありません。
- 5 個目の質問について、 30 \times 1 \times 15 \times 8 \times 6 \times 10 = 216000 は立方数です。
Score : 600 points
Problem Statement
Given a sequence A of N numbers, answer the following Q questions.
- In the i-th question, you are given integers L_i and R_i. Is A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i} a cubic number?
Here, a positive integer x is said to be a cubic number when there is a positive integer y such that x=y^3.
Constraints
- All values in input are integers.
- 1 \le N,Q \le 2 \times 10^5
- 1 \le A_i \le 10^6
- 1 \le L_i \le R_i \le N
Input
Input is given from Standard Input in the following format:
N Q A_1 A_2 \dots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
Output
Print Q lines.
The i-th line should contain Yes if, in the i-th question, A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i} is a cubic number, and No otherwise.
The checker is case-insensitive; output can be either uppercase or lowercase.
Sample Input 1
8 5 7 49 30 1 15 8 6 10 1 2 2 3 4 4 5 8 3 8
Sample Output 1
Yes No Yes No Yes
- For the first question, 7 \times 49 = 343 is a cubic number.
- For the second question, 49 \times 30 = 1470 is not a cubic number.
- For the third question, 1 is a cubic number.
- For the fourth question, 15 \times 8 \times 6 \times 10 = 7200 is not a cubic number.
- For the fifth question, 30 \times 1 \times 15 \times 8 \times 6 \times 10 = 216000 is a cubic number.