Divide and Equalize (Codeforces 1881D)
Tags: Math, number theory

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$$$.  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$$$ = [$$$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$$$].  After performing these operations, all elements in the array $$$a$$$ become equal to $$$10$$$.

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).

Note: The first test case is explained in the problem statement.

Sample Inputs:
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

Sample Outputs:
YES
YES
NO
YES
NO
YES
NO

Solution (Python):
from math import log, exp, gcd

def test(n, xs):
    root = exp(sum((log(x) for x in xs)) / n)
    if abs(root - round(root)) > 1e-05:
        return False
    return all((x == 1 or gcd(x, round(root)) != 1 for x in xs))

def task():
    n = int(input())
    xs = [int(x) for x in input().split()]
    print('YES' if test(n, xs) else 'NO')
for _ in range(int(input())):
    task()

Solution (Python):
import math
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    x = 1
    for i in l:
        x *= i
    if round(2 ** (math.log(x, 2) / n)) ** n == x:
        print('YES')
    else:
        print('NO')

Solution (Python):
from math import exp, log
Tnt = int(input())
for _ in range(Tnt):
    n = int(input())
    s = [int(x) for x in input().split()]
    prod = 1
    for i in s:
        prod *= i
    valid = round(exp(log(prod) / n)) ** n == prod
    if valid:
        print('YES')
    else:
        print('NO')