← 返回题目列表

Codeforces · 1656/C

C. 与 Mod 相等

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

给定一个 $$$n$$$ 非负整数数组 $$$a_1, a_2, \ldots, a_n$$$。可以进行如下操作:选择一个整数 $$$x \geq 2$$$,并将数组中的每个数字替换为该数字除以 $$$x$$$ 时的余数,即对于所有 $$$1 \leq i \leq n$$$ 将 $$$a_i$$$ 设置为 $$$a_i \bmod x$$$。

确定是否可以通过应用运算零次或多次来使数组的所有元素相等。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$),其中 $$$a_i$$$ 是数组的第 $$$i$$$ 元素。

所有测试用例的 $$$n$$$ 总和最多为 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以通过应用该操作使列表中的所有元素相等,则打印一行“YES”。否则,打印NO。

您可以在任何情况下打印每个字母(例如,“YES”、“Yes”、“yes”、“yEs”都将被识别为肯定答案)。

示例

输入 #1

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

输出 #1

YES
YES
NO
YES

注意

在第一个测试用例中,可以通过 $$$x = 3$$$ 运算得到数组 $$$[2, 2, 0, 2]$$$,然后通过 $$$x = 2$$$ 运算得到 $$$[0, 0, 0, 0]$$$。

在第二个测试用例中,所有数字已经相等。

在第四个测试用例中,应用 $$$x = 4$$$ 运算会产生数组 $$$[1, 1, 1, 1]$$$。