310751: CF1881D. Divide and Equalize
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$.
OutputFor 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).
ExampleInput7 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 1Output
YES YES NO YES NO YES NONote
The first test case is explained in the problem statement.
Output
1. 选择数组中的两个不同元素 $a_i$ 和 $a_j$;
2. 选择 $a_i$ 的一个除数 $x$,即 $a_i \mod x = 0$;
3. 将 $a_i$ 替换为 $\frac{a_i}{x}$,将 $a_j$ 替换为 $a_j \cdot x$。
判断是否可以通过零次或多次操作使得数组中所有元素相等。
输入数据格式:第一行包含一个整数 $t$($1 \le t \le 2000$),表示测试用例的数量。接下来是每个测试用例的描述。每个测试用例的第一行包含一个整数 $n$($1 \le n \le 10^4$),表示数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_i$($1 \le a_i \le 10^6$),表示数组 $a$ 的元素。所有测试用例的 $n$ 之和不超过 $10^4$。
输出数据格式:对于每个测试用例,输出一行。如果可以通过上述操作使得数组中所有元素相等,输出 "YES",否则输出 "NO"。输出大小写不敏感。题目大意:给定一个由正整数组成的数组 $a$,你可以对其进行以下操作: 1. 选择数组中的两个不同元素 $a_i$ 和 $a_j$; 2. 选择 $a_i$ 的一个除数 $x$,即 $a_i \mod x = 0$; 3. 将 $a_i$ 替换为 $\frac{a_i}{x}$,将 $a_j$ 替换为 $a_j \cdot x$。 判断是否可以通过零次或多次操作使得数组中所有元素相等。 输入数据格式:第一行包含一个整数 $t$($1 \le t \le 2000$),表示测试用例的数量。接下来是每个测试用例的描述。每个测试用例的第一行包含一个整数 $n$($1 \le n \le 10^4$),表示数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_i$($1 \le a_i \le 10^6$),表示数组 $a$ 的元素。所有测试用例的 $n$ 之和不超过 $10^4$。 输出数据格式:对于每个测试用例,输出一行。如果可以通过上述操作使得数组中所有元素相等,输出 "YES",否则输出 "NO"。输出大小写不敏感。