Description

给定一个长为 \(n\) 的序列 \(\{a_n\}\)，判断他们的最大公约数与最小公倍数的乘积是否等于序列中所有数的乘积。

对于所有数据，\(1\leq n\leq5\times10^5\)，\(1\leq a_i\leq10^8\)。

Solution

设 \(\displaystyle a_i=\prod p_{j}^{\alpha_{i,j}}\)，则 \(\displaystyle\gcd(a_1,a_2,a_3,\cdots,a_n)=\prod p_{j}^{\min_{i=1}^{n}\{\alpha_{i,j}\}}\)，\(\displaystyle\operatorname{lcm}(a_1,a_2,a_3,\cdots,a_n)=\prod p_{j}^{\max_{i=1}^{n}\{\alpha_{i,j}\}}\)。

若 \(\displaystyle g\times l=\prod_{i=1}^{n}a_i\)，则对于所有质数 \(p_j\) 都有 \(\displaystyle \min_{i=1}^{n}\{\alpha_{i,j}\}+\max_{i=1}^{n}\{\alpha_{i,j}\}=\sum_{i=1}^{n}\alpha_{i,j}\)。

显然对于 \(n=2\) 条件成立，否则该条件成立仅当 \(\{\alpha\}\) 中仅有一个数不为 \(0\)，也就是每个质数至多是一个 \(a_i\) 的质因子。

Pollard's Rho 不知道为什么挂了，筛出 \(\sqrt{a_i}\) 以下的素数暴力分解就行了。

时间复杂度 \(\mathcal{O}(\dfrac{n\sqrt{a_i}}{\ln a_i})\)。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Cadmus {
    typedef long long LL;
    const int N = 1e6 + 5;
    int n, cnt, qwq[N], a[N], prime[N];
    unordered_set<int> S;
    void sieve(int n) {
    	for (int i = 2; i <= n; i ++) {
		    if (!prime[i]) a[++ cnt] = i;
		    for (int j = 1; j <= cnt && i * a[j] <= n; j ++) {
		        prime[i * a[j]] = true;
		        if (i % a[j] == 0) break;
		    }
		}
	}
    int main() {
        cin >> n, S.clear();
        for (int i = 1; i <= n; i ++) cin >> qwq[i];
        if (n == 2) return puts("Yes"), 0;
        for (int i = 1; i <= n; i ++) {
        	for (int j = 1; a[j] * a[j] <= qwq[i]; j ++) {
        		if (qwq[i] % a[j]) continue;
        		if (S.count(a[j])) return puts("No"), 0;
        		S.insert(a[j]);
        		while (qwq[i] % a[j] == 0) qwq[i] /= a[j];
			}
			if (qwq[i] == 1) continue;
        	if (S.count(qwq[i])) return puts("No"), 0;
        	S.insert(qwq[i]);
		}
		puts("Yes");
        return 0;
    }
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    int T = 1; cin >> T, Cadmus::sieve(1e5);
    while (T --) Cadmus::main();
    return 0;
}