AT_abc238_g [ABC238G] Cubic?

题目描述

给定一个长度为 $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$。

输入格式

输入以以下格式从标准输入给出。

$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

输入 #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 \leq N, Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^6$
• $1 \leq L_i \leq R_i \leq N$

样例解释 1

• 对于第 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$ 是立方数。

由 ChatGPT 4.1 翻译