题目描述

难度分:$1300$

输入$T(\leq 2000)$表示$T$组数据。所有数据的$n$之和$\leq 10^4$。

每组数据输入$n(1 \leq n \leq 10^4)$和长为$n$的数组$a(1 \leq a[i] \leq 10^6)$。

你可以执行如下操作任意次：

• 选择$a[i]$和$a[j](i \neq j)$，以及$a[i]$的一个因子$x$。然后执行$a[i]=a[i]/x$和$a[j]=a[j] \times x$。

能否使$a$中所有元素都相同？输出YES或NO。

输入样例

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

输出样例

YES
YES
NO
YES
NO
YES
NO

算法

分解质因数

比较容易想歪，其实不要去考虑乘法除法，当对$a[i]$除以$x$时就会少一个因子$x$，而$a[j]$会多一个因子$x$。所以不管怎么操作，因子的数量都是守恒的，我们把每个数分解质因数，统计这些质因子的频数，只要每个质因子的频数都能被$n$整除就可以了。

复杂度分析

时间复杂度

分解每个$a[i]$使用$Pollard$ $Rho$算法，之间复杂度为$O(U^{\frac{1}{4}})$，其中$U$是$a[i]$的值域。$n$个数分解质因数，时间复杂度大约就是$O(nU^{\frac{1}{4}})$。

之后统计所有质因数的频数，在$\leq 10^6$的范围内，数字的质因数个数是很少的，基本上只有几个，可以看成每个$a[i]$只有$O(1)$级别的质因数个数，所以遍历$O(n)$级别的质因数时间复杂度还是$O(n)$。

综上，整个算法的时间复杂度大约为$O(nU^{\frac{1}{4}})$。

空间复杂度

空间瓶颈在于需要哈希表存所有$a[i]$的质因数频数，根据上面时间复杂度的分析，额外空间复杂度粗略估计为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 10010;
int T, n, a[N];

// Miller-Rabin算法判断质数
LL fast_power(__int128 a, LL k, LL p) {
    LL res = 1 % p;
    while(k) {
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

bool miller_rabin(LL n) {
    if(n == 2) return true;
    if(n <= 1 || n % 2 == 0) return false;
    LL base[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    LL u = n - 1, k = 0;
    while(!(u&1)) u >>= 1, k++;
    for(auto&x: base) {
        if(x % n == 0) continue;
        LL v = fast_power(x, u, n);
        if(v == 1 || v == n - 1) continue;
        for(int j = 1; j <= k; j++) {
            LL last = v;
            v = (__int128)v * v % n;
            if(v == 1) {
                if(last != n - 1) return false;
                break;
            }
        }
        if(v != 1) return false;
    }
    return true;
}

// Pollard-Rho分解质因数
LL Pollard_Rho(LL n) {
    static mt19937_64 sj(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<LL> u0(1, n - 1);
    LL c = u0(sj);
    auto f = [&](LL x) {
        return ((__int128)x * x + c) % n;
    };
    LL x = f(0), y = f(x);
    while(x != y) {
        LL d = __gcd(abs(x - y), n);
        if(d != 1) return d;
        x = f(x), y = f(f(y));
    }
    return n;
}

void get_factor(LL n, unordered_map<LL, int>& counter) {
    if(n == 1) return;
    if(n == 4) {
        counter[2] += 2;
        return;
    }
    if(miller_rabin(n)) {
        counter[n] += 1;
        return;
    }
    LL x = n;
    while(x == n) x = Pollard_Rho(n);
    get_factor(x, counter);
    get_factor(n/x, counter);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1);
        if(a[1] == a[n]) {
            puts("YES");
            continue;
        }
        unordered_map<int, unordered_map<LL, int>> mp;
        unordered_map<LL, int> counter;
        for(int i = 1; i <= n; i++) {
            unordered_map<LL, int> temp;
            if(mp.count(a[i])) {
                temp = mp[a[i]];
            }else {
                get_factor(a[i], temp);
                mp[a[i]] = temp;
            }
            for(auto&[num, cnt]: temp) {
                counter[num] += cnt;
            }
        }
        bool ok = true;
        for(auto&[num, cnt]: counter) {
            if(cnt % n) {
                ok = false;
                break;
            }
        }
        puts(ok? "YES": "NO");
    }
    return 0;
}