#P1881D. Divide and Equalize
Divide and Equalize
题面翻译
题目大意
给你一个包含 个正整数的数组 ,你可以进行以下操作:
- 选两个数和 (且)
- 选择的一个因数
- 将替换为,替换为
请判断是否能通过有限次操作使 中所有元素相同(可以是次)。
例如:
共个数,那么进行以下两次操作:
- 选择,则,变为
- 选择,则$a_3=\frac{a_1}{x}=\frac{100}{10}=10,a_2=1\cdot10=10$,变为
经过以上操作后,里面的元素都变成了
输入格式
第一行输入一个整数(),表示有组数据
下面每组数据:
- 第一行输入
- 第二行输入个以空格为间隙的数字,即的内容 数据保证数组中的数
输出格式
对于每组数据,判断是否可以通过有限次操作使得数组中的数均相等。可以输出“YES”,否则输出“NO”。不区分大小写。
提示:
第一组样例数据已在“题目大意”中有解释。
题目描述
You are given an array consisting of positive integers. You can perform the following operation on it:
- Choose a pair of elements and ( and );
- Choose one of the divisors of the integer , i.e., an integer such that ;
- Replace with and with .
Determine whether it is possible to make all elements in the array the same by applying the operation a certain number of times (possibly zero).For example, let's consider the array = [ ] with elements. Perform two operations on it:
- Choose and , . Replace with , and with . The resulting array is = [ ];
- Choose and , . Replace with , and with . The resulting array is = [ ].
After performing these operations, all elements in the array become equal to .
输入格式
The first line of the input contains a single integer ( ) — the number of test cases.
Then follows the description of each test case.
The first line of each test case contains a single integer ( ) — the number of elements in the array .
The second line of each test case contains exactly integers ( ) — the elements of the array .
It is guaranteed that the sum of over all test cases does not exceed .
输出格式
For each test case, output a single line:
- "YES" if it is possible to make all elements in the array equal by applying the operation a certain (possibly zero) number of times;
- "NO" otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer).
样例 #1
样例输入 #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
提示
The first test case is explained in the problem statement.
相关
在以下作业中: