codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.