正经题解｜寻找排列

题目分析

对于一对数来说，如果他们含有共同的因子，且大于1，则不互质。
用一个map来记录出现过的因子，由于并不是所有的因子都需要被记录，比如一个数有因子 $4$，那么这个数也有 $4$ 的因子 $2$，如 $12$ 有因子 $1，2，3，4，6，12$，存在因子 $4$ 必然用时存在 $4$ 的因子 $2$，存在因子 $6$，必然同时存在 $6$ 的因子 $3$。

其中 $4，6，12$ 不需要被记录，因为我们可以找到更小的因子 $2,3$，显然只需要记录所有的质因子即可。我们可以用埃氏筛先记录所有 $\leq \sqrt{N}$ 质数，再对每个数进行因子的统计。

这里可以分成两种情况。数$a_i \leq \sqrt{N}$，直接记录。数$a_i \gt \sqrt{N}$，要除尽所有的质因子，剩下的数如果 $\gt 1$，则说明这个数存在一个 $\gt \sqrt{N}$ 的质因子，也需要被记录。

最终如果质因子出现的次数大于 $1$，则说明出现了不互质的数。

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;
}

复杂度