← 返回题目列表

Codeforces · 1933/D

D. 海龟坚韧:持续模组

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

给定一个数组 $$$a_1, a_2, \ldots, a_n$$$,确定是否可以将其元素重新排列为 $$$b_1, b_2, \ldots, b_n$$$,使得 $$$b_1 \bmod b_2 \bmod \ldots \bmod b_n \neq 0$$$。

这里 $$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 所得的余数。此外,模运算是从左到右计算的。也就是说,$$$x \bmod y \bmod z = (x \bmod y) \bmod z$$$。例如,$$$2024 \bmod 1000 \bmod 8 = (2024 \bmod 1000) \bmod 8 = 24 \bmod 8 = 0$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。

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

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

输出

对于每个测试用例,如果可能,则输出“YES”,否则输出“NO”。

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

示例

输入 #1

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

输出 #1

YES
NO
YES
NO
YES
NO
YES
NO

注意

在第一个测试用例中,将数组重新排列为 $$$b = [1, 2, 3, 4, 5, 6]$$$ (什么都不做)将导致 $$$1 \bmod 2 \bmod 3 \bmod 4 \bmod 5 \bmod 6 = 1$$$。因此,达到目标是可能的。

在第二个测试用例中,数组 $$$b$$$ 必须等于 $$$[3, 3, 3, 3, 3]$$$,这将导致 $$$3 \bmod 3 \bmod 3 \bmod 3 \bmod 3 = 0$$$。因此,不可能实现目标。

在第三个测试用例中,将数组重新排列为 $$$b = [3, 2, 2]$$$ 将得到 $$$3 \bmod 2 \bmod 2 = 1$$$。因此,达到目标是可能的。