CF1771C Hossam and Trainees 题解

题目链接：CF1771C Hossam and Trainees

题意：

cxy 有 \(n\) 个学员。她为第 \(i\) 个学员指定了一个数字 \(a_i\)。

如果存在一个整数 \(x(x \geq 2)\)，满足 \(x\) 能同时整除 \(a_i\) 和 \(a_j\)，则第 \(i\) 个和第 \(j\) 个学员构成一对成功的学员。

cxy 想知道是否存在一对成功的学员。

由于 cxy 现在非常累（因为和妹纸玩了很久），她请求你的帮助！

输入格式

输入包含多个测试用例。第一行包含一个整数 \(t\left(1 \leq t \leq 10^5\right)\)，表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 \(n\left(2 \leq n \leq 10^5\right)\)。 每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)（\(1 \leq a_i \leq 10^9\)）。 保证所有测试用例中 \(n\) 的总和不超过 \(10^5\)。

输出格式

输出答案，如果存在一对成功的学员则输出 YES（不区分大小写），否则输出 NO。

如果所有的数都互质，那么不可能有任何一个素因数出现在两个数中。

我们可以对每个数暴力分解，然后标记一下。如果之前出现过，就 fail 了。

时间复杂度 \(\mathcal{O}\left(n\sqrt{M} + n \log n\right)\) ，其中 \(M\) 为 \(a_i\) 的值域

如果直接全用 map 维护的话，复杂度会变成 \(\mathcal{O}\left(n\sqrt{M} + n \omega(M)\log n\right)\) ，其中 \(\omega(10^9) = 9\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define M ((int)(4e4 + 15))

int n,cnt,a[N],p[M],vis[M]; char ck[M]; map<int,char> mp;
void init(int len)
{
    for(int i = 2; i <= len; i++)
    {
        if(!ck[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt && i * p[j] <= len; j++)
            if(ck[i * p[j]] = 1, i % p[j] == 0) break;
    }
}
void solve()
{
    cin >> n; mp.clear(); static int tim = 0; ++tim;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int k = 1,x = a[k]; k <= n; x = a[++k])
    {
        for(int i = 1; i <= cnt && p[i] <= x; i++)
        {
            if(x % p[i] != 0) continue;
            if(vis[p[i]] == tim) {
                return cout << "YES" << '\n', void(0);
            } else { vis[p[i]] = tim; while(x % p[i] == 0) x /= p[i]; }
        }
        if(x > 1) {
            if(mp.count(x)){
                return cout << "YES" << '\n', void(0);
            } else mp[x] = 1;
        }
    }
    cout << "NO" << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; init(33333); while(Q--) solve();
    return 0;
}