hlep[A C++ problem]

[China-Cy]

Select Topic Area

Question

Body

Title: Eliminating a Sequence of Numbers

Problem Description:

Given a sequence of length $n$, $a$.

A single operation is defined as selecting three integers $x,y,z\in[1,n]$, where $\gcd(a_x,a_y)=a_z$ and $x,y,z$ are all different, and then eliminating $a_z$ (i.e., $a_z$ cannot be selected for further operations).

Is it possible to eliminate $n-2$ numbers from the sequence $a_1\sim a_n$ after a certain number of operations?

Input Format:

The first line contains a positive integer $T$, indicating the number of data sets.

For each data set,

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_i$.

Output Format:

For each data set, output a line with a string Yes or No.

Sample Input:

2
3
1 2 3
3
1 2 4

Sample Output:

Yes
No

Hint:

• For the first data set, it can be achieved by eliminating $1$ with $(2,3)$.
• For the second data set, it can be proven that there is no solution.

Data Range:

This problem has $20$ test cases, each with a score of $5$.

For $100%$ of the data, $1\le T\le 10^5$, $2\leq n \leq 10^6$, $2 \le \sum n\le 10^6$, $1\le a_i\le 10^9$.

[China-Cy]

#include
#include

using namespace std;

int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

bool can_eliminate(int a[], int n) {
// If there are at least three different numbers, we can always find a solution.
if (n > 2) {
return true;
}
// If there are only two numbers, we cannot perform the operation.
if (n == 2) {
return false;
}
// If there is only one number, we can eliminate all but one.
return true;
}

int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
cout << (can_eliminate(a, n) ? "Yes" : "No") << endl;
}
return 0;
}

[China-Cy]

This is the wrong code

[aelnosu]

Is the code wrong because it does not compile or it failed at CI.

[China-Cy]

怎么改？

[aelnosu]

The first thing I notice about the code is that the #include statement are not complete.

[China-Cy]

Can you give me the correct code

[aelnosu]

bool can_eliminate(int a[], int n) {
if (n <= 2) {
return false;
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (gcd(a[i] * a[j], a[i] * a[k]) == a[j] &&
gcd(a[i] * a[j], a[j] * a[k]) == a[k] &&
gcd(a[i] * a[k], a[j] * a[k]) == a[i]) {
return true;
}
}
}
}
return false;
}

[aelnosu]

bool can_eliminate(int a[], int n) { if (n <= 2) { return false; } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (gcd(a[i] * a[j], a[i] * a[k]) == a[j] && gcd(a[i] * a[j], a[j] * a[k]) == a[k] && gcd(a[i] * a[k], a[j] * a[k]) == a[i]) { return true; } } } } return false; }