Yet Another Array Problem

Let’s strip the problem down to what it actually asks.

We need the smallest integer $x \ge 2$ such that for some array element $a_i$,

$$\gcd(a_i,x)=1.$$

That means $a_i$ and $x$ share no prime factor.

Key Observation

The answer is always prime.

Suppose some composite number $x$ works. Then there is an index $i$ such that

$$\gcd(a_i,x)=1.$$

Now take any prime divisor $p$ of $x$.

Since $p \mid x$, if $p$ also divided $a_i$, then $a_i$ and $x$ would share $p$, making the gcd bigger than $1$. But they do not share anything, so:

$$\gcd(a_i,p)=1.$$

So $p$ also works.

And because $x$ is composite, $p < x$.

So any composite valid answer can be replaced by a smaller prime valid answer. In other words, composites are useless here. They look tempting, but nope, they’re just decorative trash.

So we only need to find the smallest prime $p$ that works.

When Does A Prime Fail?

For a prime $p$:

$$\gcd(a_i,p)=1$$

is true exactly when $p \nmid a_i$.

So $p$ works if there exists some $a_i$ not divisible by $p$.

Equivalently, $p$ fails if every array element is divisible by $p$.

That condition is exactly:

$$p \mid \gcd(a_1,a_2,\dots,a_n).$$

Let

$$g = \gcd(a_1,a_2,\dots,a_n).$$

Then:

• if $p \mid g$, every $a_i$ is divisible by $p$, so $p$ fails;
• if $p \nmid g$, at least one $a_i$ is not divisible by $p$, so $p$ works.

Therefore the answer is simply:

$$\text{smallest prime } p \text{ such that } g \bmod p \ne 0.$$

Why Checking Only Small Primes Is Enough

Each $a_i \le 10^{18}$, so $g \le 10^{18}$.

If $g$ were divisible by many small primes, it would have to be at least their product. The product

$$2\cdot3\cdot5\cdot7\cdots47$$

is already huge, and multiplying by $53$ exceeds $10^{18}$. So the first prime not dividing $g$ is definitely very small, at most $53$.

In code, we can just keep a short list of primes like up to $97$ and find the first one not dividing $g$. The fallback -1 will never actually be reached for valid constraints, but printing it is harmless and matches the statement.

Algorithm

For each test case:

1. Read all numbers.
2. Compute their global gcd $g$.
3. Check primes in increasing order.
4. Print the first prime $p$ with $g \bmod p \ne 0$.

Complexity

Computing the gcd takes:

$$O(n \log A)$$

where $A \le 10^{18}$.

Checking the fixed prime list is $O(1)$.

Total over all test cases:

$$O\left(\sum n \log A\right),$$

which is easily fine.