102386: [AtCoder]ABC238 G - Cubic?

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.

问题描述

给你一个包含 $N$ 个数字的序列 $A$，回答以下 $Q$ 个问题。

• 在第 $i$ 个问题中，给你整数 $L_i$ 和 $R_i$。$A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i}$ 是一个立方数吗？

这里，正整数 $x$ 被称为立方数，当且仅当存在正整数 $y$，使得 $x=y^3$。

约束条件

• 输入中的所有值都是整数。
• $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$ 行应该包含 Yes，如果在第 $i$ 个问题中，$A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i}$ 是一个立方数，否则包含 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

• 对于第一个问题，$7 \times 49 = 343$ 是一个立方数。
• 对于第二个问题，$49 \times 30 = 1470$ 不是一个立方数。
• 对于第三个问题，$1$ 是一个立方数。
• 对于第四个问题，$15 \times 8 \times 6 \times 10 = 7200$ 不是一个立方数。
• 对于第五个问题，$30 \times 1 \times 15 \times 8 \times 6 \times 10 = 216000$ 是一个立方数。