← 返回题目列表

Codeforces · 1881/D

D. 划分和均衡

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

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。您可以对其进行如下操作:

1. 选择一对元素 $$$a_i$$$ 和 $$$a_j$$$ ($$$1 \le i, j \le n$$$ 和 $$$i \neq j$$$);
2. 选择整数 $$$a_i$$$ 的约数之一,即整数 $$$x$$$ 使得 $$$a_i \bmod x = 0$$$;
3. 将 $$$a_i$$$ 替换为 $$$\frac{a_i}{x}$$$,并将 $$$a_j$$$ 替换为 $$$a_j \cdot x$$$。

例如,我们考虑数组 $$$a$$$ = [$$$100, 2, 50, 10, 1$$$] 和 $$$5$$$ 元素。对其执行两个操作:

1. 选择 $$$a_3 = 50$$$ 且 $$$a_2 = 2$$$、$$$x = 5$$$。将 $$$a_3$$$ 替换为 $$$\frac{a_3}{x} = \frac{50}{5} = 10$$$,并将 $$$a_2$$$ 替换为 $$$a_2 \cdot x = 2 \cdot 5 = 10$$$。结果数组是 $$$a$$$ = [$$$100, 10, 10, 10, 1$$$];
2. 选择 $$$a_1 = 100$$$ 且 $$$a_5 = 1$$$、$$$x = 10$$$。将 $$$a_1$$$ 替换为 $$$\frac{a_1}{x} = \frac{100}{10} = 10$$$,并将 $$$a_5$$$ 替换为 $$$a_5 \cdot x = 1 \cdot 10 = 10$$$。结果数组是 $$$a$$$ = [$$$10, 10, 10, 10, 10$$$]。

输入

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

然后是每个测试用例的描述。

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

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

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

输出

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

- 如果可以通过应用一定次数(可能为零)的操作使数组中的所有元素相等,则为“是”;
- 否则为“否”。

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

示例

输入 #1

7
5
100 2 50 10 1
3
1 1 1
4
8 2 4 2
4
30 50 27 20
2
75 40
2
4 4
3
2 3 1

输出 #1

YES
YES
NO
YES
NO
YES
NO

注意

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