Divide and Equalize
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given an array $a$ consisting of $n$ positive integers. You can perform the following operation on it:
- Choose a pair of elements $a_i$ and $a_j$ ($1 \le i, j \le n$ and $i \neq j$);
- Choose one of the divisors of the integer $a_i$, i.e., an integer $x$ such that $a_i \bmod x = 0$;
- Replace $a_i$ with $\frac{a_i}{x}$ and $a_j$ with $a_j \cdot x$.
For example, let's consider the array $a$ = [$100, 2, 50, 10, 1$] with $5$ elements. Perform two operations on it:
- Choose $a_3 = 50$ and $a_2 = 2$, $x = 5$. Replace $a_3$ with $\frac{a_3}{x} = \frac{50}{5} = 10$, and $a_2$ with $a_2 \cdot x = 2 \cdot 5 = 10$. The resulting array is $a$ = [$100, 10, 10, 10, 1$];
- Choose $a_1 = 100$ and $a_5 = 1$, $x = 10$. Replace $a_1$ with $\frac{a_1}{x} = \frac{100}{10} = 10$, and $a_5$ with $a_5 \cdot x = 1 \cdot 10 = 10$. The resulting array is $a$ = [$10, 10, 10, 10, 10$].
The first line of the input contains a single integer $t$ ($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$ ($1 \le n \le 10^4$) — the number of elements in the array $a$.
The second line of each test case contains exactly $n$ integers $a_i$ ($1 \le a_i \le 10^6$) — the elements of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $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).
Input
The first line of the input contains a single integer $t$ ($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$ ($1 \le n \le 10^4$) — the number of elements in the array $a$.
The second line of each test case contains exactly $n$ integers $a_i$ ($1 \le a_i \le 10^6$) — the elements of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.
Output
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).
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
YES
YES
NO
YES
NO
YES
NO
Note
The first test case is explained in the problem statement.
20240121CFdiv3.1881
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 7
- Start at
- 2024-1-21 14:45
- End at
- 2024-1-21 17:30
- Duration
- 2.8 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 18