题目 | Hossam and Trainees
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
A pair of the
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
The first line of each test case contains an integer number
The second line of each test case contains
It is guaranteed that the sum of
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.
Example
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:
题解
典型错解 - 看起来仿佛是
拿到题目一眼看到就想到把整个数列求一个和得到
但是该解发存在的问题就是连续乘法会让数字大小呈指数趋势增长,
正确解法 -
将数列中每个数分解质因数,如果有任意两个数含有同一个质因子,则输出 YES,如果所有数都没有公共的质因子,则输出 NO.
从头到尾遍历数列,使用集合
来储存出现过的质因子:- 对于每个数,分解质因数得到:
考虑其所有的质因子:
- 若质因子
已经在 中:直接输出 YES,结束本次计算 - 若质因子
不在 中:将 加入
- 若质因子
- 对于每个数,分解质因数得到:
- 若遍历完整个数列后还没有找到相同的质因子,则输出 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;
}
本文采用 CC BY-SA 4.0 许可,本文 Markdown 源码:Haotian-BiJi