← 返回题目列表

Codeforces · 1714/E

E. 添加模 10

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

给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \dots, a_n$$$

您可以任意次数应用以下操作:

- 选择索引 $$$i$$$ ($$$1 \le i \le n$$$) 并将元素 $$$a_i$$$ 的值替换为值 $$$a_i + (a_i \bmod 10)$$$,其中 $$$a_i \bmod 10$$$ 是整数除以 $$$a_i$$$ 的余数$$$10$$$。

对于单个索引(值 $$$i$$$),可以多次应用此操作。如果该操作重复应用于同一索引,则每次都会考虑 $$$a_i$$$ 的当前值。例如,如果$$$a_i=47$$$,则在第一次操作后我们得到$$$a_i=47+7=54$$$,在第二次操作后我们得到$$$a_i=54+4=58$$$。

检查是否可以通过应用多个(可能为零)运算使所有数组元素相等。

例如,您有一个数组 $$$[6, 11]$$$。

- 让我们将此操作应用于数组的第一个元素。我们将 $$$a_1 = 6$$$ 替换为 $$$a_1 + (a_1 \bmod 10) = 6 + (6 \bmod 10) = 6 + 6 = 12$$$。我们得到数组$$$[12, 11]$$$。
- 然后将此操作应用于数组的第二个元素。我们将 $$$a_2 = 11$$$ 替换为 $$$a_2 + (a_2 \bmod 10) = 11 + (11 \bmod 10) = 11 + 1 = 12$$$。我们得到数组 $$$[12, 12]$$$。

因此,通过应用 $$$2$$$ 运算,可以使数组的所有元素相等。

输入

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

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

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

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

输出

对于每个测试用例打印:

- 如果可以使所有数组元素相等,则为 YES;
- 否则不。

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

示例

输入 #1

10
2
6 11
3
2 18 22
5
5 10 5 10 5
4
1 2 4 8
2
4 5
3
93 96 102
2
40 6
2
50 30
2
22 44
2
1 5

输出 #1

Yes
No
Yes
Yes
No
Yes
No
No
Yes
No

注意

第一个测试用例已在上面阐明。

在第二个测试用例中,不可能使所有数组元素相等。

在第三个测试用例中,您需要对等于 $$$5$$$ 的所有元素应用一次此操作。

在第四个测试用例中,您需要将此操作应用于所有元素,直到它们等于 $$$8$$$。

在第五个测试用例中,不可能使所有数组元素相等。

在第六个测试用例中,您需要将此操作应用于所有元素,直到它们等于 $$$102$$$。