题目：Random

思路：

暴力法不可行：直接枚举所有元素对的时间复杂度为 𝑂(𝑛)O(n ) ，在 𝑛=×n=2×10 时会超时。 利用素数分解：若两个数的 GCD 大于 1，则它们至少有一个公共素因子。因此，可以遍历每个数的素因子，统计每个素因子出现的次数。若某个素因子出现在至少两个数中，则这两个数满足条件。 优化素数分解：每个数的素因子个数不超过 log()≈log ​ (10 )≈30 ，因此总时间复杂度为 𝑂 ( 𝑛 × log ⁡ 𝑎 𝑖 ) O(n×loga i ​ ) ，可接受。

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; vector sieve(int max_n) { vector primes; vector is_prime(max_n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= max_n; ++i) { if (is_prime[i]) { primes.push_back(i); for (int j = i * i; j <= max_n; j += i) { is_prime[j] = false; } } } return primes; } vector prime_factors(int x, const vector& primes) { vector factors; for (int p : primes) { if (p * p > x) break; if (x % p == 0) { factors.push_back(p); while (x % p == 0) x /= p; } } if (x > 1) factors.push_back(x); return factors; } int main() { vector primes = sieve(31623); int T; cin >> T; while (T--) { int n; cin >> n; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } map<int, vector> factor_to_indices; for (int i = 0; i < n; ++i) { if (a[i] == 1) continue; vector factors = prime_factors(a[i], primes); for (int p : factors) { factor_to_indices[p].push_back(i); } } bool found = false; for (auto& [factor, indices] : factor_to_indices) { if (indices.size() >= 2) { cout << a[indices[0]] << " " << a[indices[1]] << "\n"; found = true; break; } } if (!found) { cout << -1 << "\n"; } } }