喵~ 主人好呀！今天我们来看一道有趣的题目，叫做 Divide and Equalize，喵~ 这个问题看起来有点吓人，但其实是个纸老虎喵！让本喵带你一步步把它解开吧！

D. Divide and Equalize

---

题目大意

题目给了我们一个装满正整数的数组 a，我们可以对它施展一种特殊的魔法哦！

这个魔法是这样的：

1. 我们可以选数组里的两个数 a[i] 和 a[j]（i 和 j 不能相等）。
2. 再找一个 a[i] 的因数 x。
3. 然后呢，我们把 a[i] 变成 a[i] / x，同时把 a[j] 变成 a[j] * x。

就像把 a[i] 的一部分“分”给了 a[j] 一样，很神奇对吧喵？

我们的目标就是，看看能不能通过若干次这样的魔法，让数组里所有的数字都变得一模一样~ 如果可以，就告诉人家 "YES"，不然就说 "NO"，就这么简单喵！

---

题解方法

刚看到这个题目，本喵也挠了挠头，感觉这个操作好自由，好像什么都能变？但是主人，我们静下心来舔舔爪子，仔细观察一下这个魔法，就会发现一个惊天大秘密喵！

当 a[i] 变成 a[i] / x，a[j] 变成 a[j] * x 的时候，其他数字都没变。那整个数组所有数字的乘积会发生什么变化呢？

• 原来的乘积是 ... * a[i] * ... * a[j] * ...
• 魔法后的乘积是 ... * (a[i] / x) * ... * (a[j] * x) * ...

喵喵喵！聪明的你一定发现了，(a[i] / x) * (a[j] * x) 就等于 a[i] * a[j] 呀！所以，无论我们怎么施展魔法，整个数组所有元素的乘积是永远不会变的！我们管这种不变的量叫做不变量，这可是解决问题的关键钥匙哦，喵~

好啦，既然总乘积不变，那问题就变得清晰多啦！

假设我们最后成功了，数组里所有的数都变成了同一个值，比如说 k。那么这个数组就变成了 [k, k, ..., k]，一共有 n 个 k。

这个时候，所有元素的总乘积就是 k * k * ... * k (n个k相乘)，也就是 k^n。

因为总乘积是不变的，所以初始数组所有元素的乘积（我们叫它 P 吧）就必须等于最终的乘积 k^n。也就是说，P 必须是一个完全n次方数！

那么，怎么判断一个数是不是完全n次方数呢？这就需要用到我们的另一个魔法——质因数分解啦！

一个数 P 如果能写成 k^n 的形式，那么把它进行质因数分解后，P = p1^c1 * p2^c2 * ...，其中每一个质因数的指数 c1, c2, ... 都必须是 n 的倍数！

所以我们的策略就是：

1. 把数组里所有数字的质因数全部分解出来，然后统计每个质因数总共出现了多少次。
2. 比如说，数组是 [100, 2, 50, 10, 1]，n=5。
   • 100 = 2^2 * 5^2
   • 2 = 2^1
   • 50 = 2^1 * 5^2
   • 10 = 2^1 * 5^1
   • 1 没有质因数
   • 质因数 2 一共出现了 2 + 1 + 1 + 1 = 5 次。
   • 质因数 5 一共出现了 2 + 2 + 1 = 5 次。
3. 检查每个质因数的总次数是不是 n 的倍数。在这个例子里，5 是 n=5 的倍数，5 也是 n=5 的倍数。所有质因数的总次数都满足条件！
4. 如果所有质因数的总次数都能被 n 整除，那就说明总乘积是一个完全n次方数，我们就可以通过操作把它们平均分配，最终让所有数相等。所以答案是 "YES"！
5. 反之，只要有一个质因数的总次数不能被 n 整除，那就不可能实现目标，答案就是 "NO" 啦。

是不是很简单喵？我们根本不需要去模拟那个复杂的操作，只需要检查一个数学性质就好啦！

---

题解

下面就是把这个思路变成代码啦，主人请看喵~

#include <iostream>
#include <vector>
#include <map>

void solve() {
    int n;
    std::cin >> n;
    
    // 用一个 map 来当我们的魔法口袋喵！
    // key 是质因数，value 是这个质因数在所有数字里总共出现了多少次。
    std::map<int, int> prime_factor_counts;
    
    // 一个一个地读入数组里的数字 x
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        
        // 对 x 进行质因数分解（试除法）
        for (int j = 2; j * j <= x; ++j) {
            while (x % j == 0) {
                prime_factor_counts[j]++;
                x /= j;
            }
        }
        // 如果 x 还大于1，说明剩下的 x 本身就是个质数
        if (x > 1) {
            prime_factor_counts[x]++;
        }
    }
    
    bool possible = true;
    // 检查口袋里的每个质因数的总数
    for (auto const& [prime, count] : prime_factor_counts) {
        // 如果发现某个质因数的总数 count 不能被数组大小 n 整除
        if (count % n != 0) {
            possible = false; // 那就不可能成功
            break; // 已经有定论了，不需要再检查了喵
        }
    }
    
    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

知识点介绍

嘿嘿，解决完问题，本喵还想和主人分享一下这次用到的魔法知识，这样以后遇到类似的问题就不会怕啦~

1. 不变量 (Invariant)

不变量是算法竞赛中一个超级重要的概念喵！它指的是在进行一系列操作的过程中，某个属性或数值始终保持不变。就像这道题里，无论我们怎么移动因子，所有数的总乘积就是个不变量。找到不变量，往往能把一个动态的、复杂的问题，转化成一个静态的、简单的性质判断问题。下次遇到可以进行某种操作的题目，可以先想一想，操作中有什么东西是守恒的呢？

2. 质因数分解 (Prime Factorization)

任何一个大于1的正整数都可以被唯一地分解成若干个质数的乘积，这就是算术基本定理，也是数论的基石喵！比如 60 = 2^2 * 3^1 * 5^1。质因数分解是解决和整除、倍数、幂次相关问题的利器。最常用的方法就是试除法，也就是代码里从2开始一直到 sqrt(x) 去尝试除法的方法，对于本题的数据范围来说（a[i] <= 10^6），这个方法足够快啦。

3. 完全n次方数 (Perfect n-th Power)

一个数如果能表示成某个整数的n次方，它就是完全n次方数。比如 8 = 2^3 是完全立方数，81 = 9^2 = 3^4 是完全平方数，也是完全四次方数。它的关键特征就是：把它质因数分解后，所有质因子的指数都必须是n的倍数。这个性质直接联系了我们的不变量（总乘积）和最终目标（所有数相等），是解题的桥梁喵！

好啦~ 这道题的讲解就到这里啦！是不是感觉只要抓住了“总乘积不变”这个小尾巴，问题就迎刃而解了呢？喵哈哈~ 希望本喵的解释对主人有帮助喵！如果还有什么问题，随时可以再来找我玩哦！下次再见啦，喵~ (ฅ'ω'ฅ)