Sieve of Erato67henes

Research check: the official Codeforces problem, the Codeforces Round 1080 editorial, Arpa's tutorial page linking an accepted submission, and public accepted-style solutions all point to the same intended approach: just check whether 67 appears. The community explanation also frames the same prime-number observation. No need to cosplay as Eratosthenes.

We need to choose a non-empty subset of the given positive integers so that its product is exactly $67$.

The key fact is:

$67 \text{ is prime.}$

So its only positive divisors are:

$1 \quad \text{and} \quad 67.$

Suppose some selected subset has product $67$. Pick any selected number $x$. Since all numbers are positive integers, we can write:

$x \cdot R = 67$

where $R$ is the product of the other selected numbers, also a positive integer. Therefore $x$ must divide $67$. Since $67$ is prime, $x$ must be either $1$ or $67$.

That immediately kills the common false assumption: numbers like $7$, $6$, $3$, or $5$ are not helpful. They don't combine into $67$ because $67$ has no nontrivial factorization. It's prime; the problem title is basically trolling.

Now there are two cases:

• If the array contains $67$, we can select just that one element. The product is $67$, so the answer is YES.
• If the array does not contain $67$, then every selected number that could possibly be valid would have to be $1$. But any non-empty product of only ones is $1$, not $67$. So the answer is NO.

The sample's first test has a 67, so YES. The note selects $1 \cdot 67$, but selecting only $67$ already works. In the second test there is no 67, so no subset can reach the target.

Edge cases:

• $n=1$, array is [67]: YES.
• $n=1$, array is [1]: NO because the subset must be non-empty and product is $1$.
• Many ones plus one 67: YES.
• Several composite numbers whose product gets large: irrelevant; none can multiply to a prime unless the prime itself appears.

Algorithm:

For each test case, scan the $n$ numbers and remember whether any value equals $67$.

Complexity per test case:

$O(n)$

Memory:

$O(1)$

With $n \le 5$, this is wildly under the limit. The CPU is basically on vacation.