← 返回题目列表

Codeforces · 1980/D

D. GCD 序列

中文机器翻译题面 查看原题

两个整数 $$$x$$$ 和 $$$y$$$ 的 GCD(最大公约数)是 $$$x$$$ 和 $$$y$$$ 均可整除的最大整数 $$$z$$$。例如,$$$GCD(36, 48) = 12$$$、$$$GCD(5, 10) = 5$$$ 和 $$$GCD(7,11) = 1$$$。

Kristina 有一个数组 $$$a$$$ 恰好由 $$$n$$$ 正整数组成。她想要计算每对相邻数字的 GCD,以获得一个新数组 $$$b$$$,称为 GCD 序列。

因此,GCD 序列 $$$b$$$ 的元素将使用公式 $$$b_i = GCD(a_i, a_{i + 1})$$$ 计算,其中 $$$1 \le i \le n - 1$$$。

确定是否可以从数组 $$$a$$$ 中恰好删除一个数字,以便 GCD 序列 $$$b$$$ 是非递减的(即 $$$b_i \le b_{i+1}$$$ 始终为 true)。

例如,让 Khristina 有一个数组 $$$a$$$ = [$$$20, 6, 12, 3, 48, 36$$$]。如果她从中删除 $$$a_4 = 3$$$ 并计算 $$$b$$$ 的 GCD 序列,她会得到:

- $$$b_1 = GCD(20, 6) = 2$$$
- $$$b_2 = GCD(6, 12) = 6$$$
- $$$b_3 = GCD(12, 48) = 12$$$
- $$$b_4 = GCD(48, 36) = 12$$$

输入

输入数据的第一行包含一个数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) - 测试中测试用例的数量。

接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 中的元素数量。

每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行:

- 如果您可以从数组 $$$a$$$ 中恰好删除一个数字,从而使 $$$b$$$ 的 GCD 序列不减,则为“是”;
- 否则为“否”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”都将被识别为肯定答案)。

示例

输入 #1

12
6
20 6 12 3 48 36
4
12 6 3 4
3
10 12 3
5
32 16 8 4 2
5
100 50 2 10 20
4
2 4 8 1
10
7 4 6 2 4 5 1 4 2 8
7
5 9 6 8 5 9 2
6
11 14 8 12 9 3
9
5 7 3 10 6 3 12 6 3
3
4 2 4
8
1 6 11 12 6 12 3 6

输出 #1

YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES

注意

第一个测试用例在问题陈述中进行了解释。