题目分析 对于一对数来说，如果他们含有共同的因子，且大于1，则不互质。 用一个map来记录出现过的因子，由于并不是所有的因子都需要被记录，比如一个数有因子 444，那么这个数也有 444 的因子 222，如 121212 有因子 1，2，3，4，6，121，2，3，4，6，121，2，3，4，6，12，存在因子 444 必然用时存在 444 的因子 222，存在因子 666，必然同时存在 666 的因子 333。 其中 4，6，124，6，124，6，12 不需要被记录，因为我们可以找到更小的因子 2,32,32,3，显然只需要记录所有的质因子即可。我们可以用埃氏筛先记录所有 ≤N\leq \sqrt{N}≤N 质数，再对每个数进行因子的统计。 这里可以分成两种情况。数ai≤Na_i \leq \sqrt{N}ai ≤N ，直接记录。数ai>Na_i \gt \sqrt{N}ai >N ，要除尽所有的质因子，剩下的数如果 >1\gt 1>1，则说明这个数存在一个 >N\gt \sqrt{N}>N 的质因子，也需要被记录。 最终如果质因子出现的次数大于 111，则说明出现了不互质的数。 AC代码 复杂度

#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int N = 1e5 + 10; const ll A = 1e9; int t,n; bitset<31666> p; vector<int> v; void init() { int r = sqrt(A); for(int i=2;i<=r;i++) { if (p[i]) { continue; } v.push_back(i); for(int j=2*i;j<=r;j+=i) { p[j] = true; } } } int main() { init(); ios::sync_with_stdio(false); cin >> t; while(t--) { cin >> n; unordered_map<int,int> vis; int flag = 0; for(int i=0;i<n;i++) { int a; cin >> a; if (!flag) { for(int &j:v) { if (a % j == 0) { vis[j]; if (vis[j] > 1) { flag = 1; } while(a % j == 0)a /= j; } } if (a != 1)vis[a]; if (vis[a] > 1) { flag = 1; } } } if (flag)cout << "YES" << endl; else cout << "NO" << endl; } return 0; }