Codeforces Round 903 (Div. 3) D. Divide and Equalize（数学）

本文主要是介绍Codeforces Round 903 (Div. 3) D. Divide and Equalize（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个由 $n$ 个正整数组成的数组 $a$ 。你可以对它进行以下操作：

选择一对元素 $a_i$ 和 $a_j$ ( $\le i, j \le n$ 和 $\neq j$ )；
选择整数 $ai$ 的除数之一，即整数 $x$ 中的 $a_i \bmod x = 0$ ；
将 $a_i$ 替换为 $\frac{a_i}{x}$ ，将 $a_j$ 替换为 $a_j \cdot x$ 。

确定是否有可能通过一定次数(可能为零)的运算使数组中的所有元素都相同。

例如，数组 $a$ = [ $100, 2, 50, 10, 1$ /]包含 $5$ 个元素。对它进行两次操作：

选择 $a_3 = 50$ 和 $a_2 = 2$ , $x = 5$ .将 $a_3$ 替换为 $\frac{a_3}{x} = \frac{50}{5} = 10$ ，将 $a_2$ 替换为 $a_2 \cdot x = 2 \cdot 5 = 10$ 。得到的数组是 $a$ = [ $100, 10, 10, 10, 1$ ]；
选择 $a_1 = 100$ 和 $a_5 = 1$ , $x = 10$ .将 $a_1$ 替换为 $\frac{a_1}{x} = \frac{100}{10} = 10$ ，将 $a_5$ 替换为 $a_5 \cdot x = 1 \cdot 10 = 10$ 。得到的数组是 $a$ = [ $10, 10, 10, 10, 10$ ]。

执行这些运算后，数组 $a$ 中的所有元素都等于 $10$ 。

输入

输入的第一行包含一个整数 $t$ ( $\le t \le 2000$ ) - 测试用例的数量。

然后是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ( $\le n \le 10^4$ ) - 数组 $a$ 中的元素个数。

每个测试用例的第二行正好包含 $n$ 个整数 $a_i$ ( $\le a_i \le 10^6$ )。( $\le a_i \le 10^6$ ) - 数组 $a$ 中的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^4$ 。

输出

为每个测试用例输出一行：

如果通过执行一定次数(可能为零)的操作可以使数组中的所有元素相等，则输出 “YES”；
否则输出 “否”。

您可以输出任何情况下的答案(例如，字符串 “yEs”、“yes”、"Yes "和 "YES "都将被识别为肯定答案)。

仔细分析两个操作可能带来的后果，如果一个数除以x之后另一个数又乘了x，那么就会导致整个数组的乘积永远不会改变。

即在这种情况下，其实是某个数的因数转移给了另一个数。

在这种条件下最终数组可以达成每个元素都相等，也就是每个元素的质因数都相同，想要实现所有数的质因数都相同，就必须进行质因数的转移，如果到最后能够转移出来，就必须满足组成数组元素的所有质因数是 n 的倍数，只有都是n的倍数才能够转移之后平均下来。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;void solve()
{int n;cin >> n;vector<int> a(n);unordered_map<int, int> primes;for (int i = 0; i < n; i++){cin >> a[i];for (int j = 2; j <= a[i] / j; j++){while (a[i] % j == 0){a[i] /= j;primes[j]++;}}if (a[i] > 1)primes[a[i]]++;}for (auto prime : primes){if (prime.second % n != 0){cout << "NO\n";return;}}cout << "YES\n";return;
}int main()
{int t;cin >> t;while (t--){solve();}return 0;
}