1881D.md (2396B)
1 Source: https://codeforces.com/problemset/problem/1881/D 2 3 D. Divide and Equalize 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ consisting of $n$ positive integers. You can perform the following operation on it: 22 23 1. Choose a pair of elements $a_i$ and $a_j$ ($1 \le i, j \le n$ and $i \neq j$); 24 2. Choose one of the divisors of the integer $a_i$, i.e., an integer $x$ such that $a_i \bmod x = 0$; 25 3. Replace $a_i$ with $\frac{a_i}{x}$ and $a_j$ with $a_j \cdot x$. 26 27 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). 28 29 For example, let's consider the array $a$ = [$100, 2, 50, 10, 1$] with $5$ elements. Perform two operations on it: 30 31 1. 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$]; 32 2. 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$]. 33 34 After performing these operations, all elements in the array $a$ become equal to $10$. 35 36 Input 37 38 The first line of the input contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases. 39 40 Then follows the description of each test case. 41 42 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$. 43 44 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$. 45 46 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$. 47 48 Output 49 50 For each test case, output a single line: 51 52 * "YES" if it is possible to make all elements in the array equal by applying the operation a certain (possibly zero) number of times; 53 * "NO" otherwise. 54 55 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). 56 57 Example 58 59 Input 60 61 ``` 62 7 63 64 5 65 66 100 2 50 10 1 67 68 3 69 70 1 1 1 71 72 4 73 74 8 2 4 2 75 76 4 77 78 30 50 27 20 79 80 2 81 82 75 40 83 84 2 85 86 4 4 87 88 3 89 90 2 3 1 91 ``` 92 93 Output 94 95 ``` 96 YES 97 YES 98 NO 99 YES 100 NO 101 YES 102 NO 103 ``` 104 105 Note 106 107 The first test case is explained in the problem statement.