#P1881D. Divide and Equalize

Divide and Equalize

题面翻译

题目大意

给你一个包含 nn 个正整数的数组 aa,你可以进行以下操作:

  1. 选两个数aia_iaja_j1i,jn1 < i, j \le niji \ne j
  2. 选择aia_i的一个因数xx
  3. aia_i替换为aix\frac{a_i}{x}aja_j替换为ajxa_j \cdot x

请判断是否能通过有限次操作使 aa 中所有元素相同(可以是00次)。

例如:

a=[100,2,50,10,1]a=[100,2,50,10,1]55个数,那么进行以下两次操作:

  1. 选择a3=50,a2=2,x=5a_3=50,a_2=2,x=5,则a3=a3x=505=10,a2=25=10a_3=\frac{a_3}{x}=\frac{50}{5}=10,a_2=2\cdot5=10aa变为[100,10,10,10,1][100,10,10,10,1]
  2. 选择a1=100,a5=1,x=10a_1=100,a_5=1,x=10,则$a_3=\frac{a_1}{x}=\frac{100}{10}=10,a_2=1\cdot10=10$,aa变为[10,10,10,10,10][10,10,10,10,10]

经过以上操作后,aa里面的元素都变成了1010

输入格式

第一行输入一个整数tt1t10001\le t\le1000),表示有tt组数据

下面每组数据:

  1. 第一行输入nn
  2. 第二行输入nn个以空格为间隙的数字,即aa的内容 数据保证1n104,a1 \le n \le 10^4,a数组中的数1ai1061 \le a_i \le 10^6

输出格式

对于每组数据,判断是否可以通过有限次操作使得aa数组中的数均相等。可以输出“YES”,否则输出“NO”。不区分大小写。

提示:

第一组样例数据已在“题目大意”中有解释。

题目描述

You are given an array a a consisting of n n positive integers. You can perform the following operation on it:

  1. Choose a pair of elements ai a_i and aj a_j ( 1i,jn 1 \le i, j \le n and ij i \neq j );
  2. Choose one of the divisors of the integer ai a_i , i.e., an integer x x such that aimodx=0 a_i \bmod x = 0 ;
  3. Replace ai a_i with aix \frac{a_i}{x} and aj a_j with ajx a_j \cdot x .

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 a a = [ 100,2,50,10,1 100, 2, 50, 10, 1 ] with 5 5 elements. Perform two operations on it:

  1. Choose a3=50 a_3 = 50 and a2=2 a_2 = 2 , x=5 x = 5 . Replace a3 a_3 with a3x=505=10 \frac{a_3}{x} = \frac{50}{5} = 10 , and a2 a_2 with a2x=25=10 a_2 \cdot x = 2 \cdot 5 = 10 . The resulting array is a a = [ 100,10,10,10,1 100, 10, 10, 10, 1 ];
  2. Choose a1=100 a_1 = 100 and a5=1 a_5 = 1 , x=10 x = 10 . Replace a1 a_1 with a1x=10010=10 \frac{a_1}{x} = \frac{100}{10} = 10 , and a5 a_5 with a5x=110=10 a_5 \cdot x = 1 \cdot 10 = 10 . The resulting array is a a = [ 10,10,10,10,10 10, 10, 10, 10, 10 ].

After performing these operations, all elements in the array a a become equal to 10 10 .

输入格式

The first line of the input contains a single integer t t ( 1t2000 1 \le t \le 2000 ) — the number of test cases.

Then follows the description of each test case.

The first line of each test case contains a single integer n n ( 1n104 1 \le n \le 10^4 ) — the number of elements in the array a a .

The second line of each test case contains exactly n n integers ai a_i ( 1ai106 1 \le a_i \le 10^6 ) — the elements of the array a a .

It is guaranteed that the sum of n n over all test cases does not exceed 104 10^4 .

输出格式

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.