← 返回题目列表

Codeforces · 1401/C

C. 纯粹的数组

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

给定一个数组 $$$a_1, a_2, \dots, a_n$$$,其中所有 $$$a_i$$$ 都是整数并且大于 $$$0$$$。

在一次操作中,您可以选择两个不同的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$)。如果$$$gcd(a_i, a_j)$$$等于整个数组$$$a$$$的最小元素,则可以交换$$$a_i$$$和$$$a_j$$$。 $$$gcd(x, y)$$$ 表示整数$$$x$$$ 和$$$y$$$ 的最大公约数(GCD)。

现在您希望使用该操作任意次数(可能为零)使 $$$a$$$ 不减。确定你是否可以做到这一点。

数组 $$$a$$$ 是非递减的当且仅当 $$$a_1 \le a_2 \le \ldots \le a_n$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 正整数 $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组本身。

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

输出

对于每个测试用例,如果可以使用所描述的操作使数组 $$$a$$$ 不减,则输出“YES”,如果不可能,则输出“NO”。

示例

输入 #1

4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4

输出 #1

YES
YES
YES
NO

注意

在第一个和第三个示例中,数组已经是非递减的。

在第二个示例中,我们可以先交换 $$$a_1$$$ 和 $$$a_3$$$,然后交换 $$$a_1$$$ 和 $$$a_5$$$ 以使数组不减。

在第四个示例中,我们无法使用该操作对数组进行非减操作。