Codeforces Round #837 (Div. 2)

C. Hossam and Trainees

https://codeforces.com/contest/1771/problem/B

3 seconds / 256 megabytes

standard input / standard output

### Problem

Hossam has $n$ trainees. He assigned a number $a_i$ for the $i$-th trainee.

A pair of the $i$-th and $j$-th ($i \neq j$) trainees is called successful if there is an integer $x$ ($x \geq 2$), such that $x$ divides $a_i$, and $x$ divides $a_j$.

Hossam wants to know if there is a successful pair of trainees.

Hossam is very tired now, so he asks you for your help!

### Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$), the number of test cases. A description of the test cases follows.

The first line of each test case contains an integer number $n$ ($2 \le n \le 10^5$).

The second line of each test case contains $n$ integers, the number of each trainee $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

### Output

Print the answer — "YES" (without quotes) if there is a successful pair of trainees and "NO" otherwise. You can print each letter in any case.

Input

2
3
32 48 7
3
14 5 9

Output

YES
NO

### Note

In the first example, the first trainee and the second trainee make up a successful pair:

$a_1 = 32, a_2 = 48$, you can choose $x = 4$.

### 题解

#### 正确解法 - $O(n\log n)$

• 从头到尾遍历数列，使用集合 $s$ 来储存出现过的质因子：

• 对于每个数，分解质因数得到：$n=p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}$
• 考虑其所有的质因子：$p_1,p_2,\dots,p_n$

• 若质因子 $p_i$ 已经在 $s$ 中：直接输出 YES，结束本次计算
• 若质因子 $p_i$ 不在 $s$ 中：将 $p_i$ 加入 $s$
• 若遍历完整个数列后还没有找到相同的质因子，则输出 NO，结束计算

### 代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MAXN = 1e5 + 10;
int a[MAXN], prime[MAXN], primesize = 0;
bool not_prime[MAXN];
void init_prime()
{
not_prime[0] = not_prime[1] = true;
for (int i = 2; i < MAXN; i++)
{
if (!not_prime[i])
prime[primesize++] = i;
for (int j = 0; j < primesize && i * prime[j] < MAXN; j++)
{
not_prime[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
}

void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
set<int> s;
for (int i = 0; i < n; i++)
{
for (int j = 0; prime[j] * prime[j] <= a[i]; j++)
{
if (!(a[i] % prime[j]))
{
if (s.find(prime[j]) != s.end())
{
cout << "YES" << endl;
return;
}
s.insert(prime[j]);
while (!(a[i] % prime[j]))
a[i] /= prime[j];
}
}
if (a[i] > 1)
{
if (s.find(a[i]) != s.end())
{
cout << "YES" << endl;
return;
}
s.insert(a[i]);
}
}
cout << "NO" << endl;
return;
}

signed main()
{
init_prime();
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}