2167D.md (2241B)
1 Source: https://codeforces.com/problemset/problem/2167/D 2 3 D. Yet Another Array Problem 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an integer $n$ and an array $a$ of length $n$. 22 23 Find the smallest integer $x$ ($2 \le x \le 10^{18}$) such that there exists an index $i$ ($1 \le i \le n$) with $\gcd$$^{\text{∗}}$$(a_i, x) = 1$. If no such $x$ exists within the range $[2,10^{18}]$, output $-1$. 24 25 $^{\text{∗}}$$\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 Each of the following $t$ test cases consists of two lines: 32 33 The first line contains a single integer $n$ ($1 \le n \le 10^{5}$) — the length of the array. 34 35 The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$). 36 37 It is guaranteed that the total sum of $n$ across all test cases does not exceed $10^{5}$. 38 39 Output 40 41 For each test case, output a single integer: the smallest $x$ ($2 \le x \le 10^{18}$) such that there exists an index $i$ with $\gcd(a_i, x) = 1$. If there is no such $x$ in the range $[2,10^{18}]$, print $-1$. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 1 51 52 1 53 54 4 55 56 6 6 12 12 57 58 3 59 60 24 120 210 61 62 4 63 64 2 4 6 10 65 ``` 66 67 Output 68 69 ``` 70 2 71 72 5 73 74 5 75 76 3 77 ``` 78 79 Note 80 81 In the first test case, $\gcd(2,1)=1$, which is the smallest number satisfying the condition. 82 83 In the second test case: 84 85 * $\gcd(2,6)=2$, $\gcd(2,12)=2$, so $2$ cannot be the answer. 86 * $\gcd(3,6)=3$, $\gcd(3,12)=3$, so $3$ cannot be the answer. 87 * $\gcd(4,6)=2$, $\gcd(4,12)=4$, so $4$ cannot be the answer. 88 * $\gcd(5,6)=1$, so the answer is $5$. 89 90 In the third test case: 91 92 * $\gcd(2,24)=2$, $\gcd(2,120)=2$, $\gcd(2,210)=2$, so $2$ cannot be the answer. 93 * $\gcd(3,24)=3$, $\gcd(3,120)=3$, $\gcd(3,210)=3$, so $3$ cannot be the answer. 94 * $\gcd(4,24)=4$, $\gcd(4,120)=4$, $\gcd(4,210)=2$, so $4$ cannot be the answer. 95 * $\gcd(5,24)=1$, so the answer is $5$. 96 97 In the fourth test case: 98 99 * $\gcd(2,2)=2$, $\gcd(2,4)=2$, $\gcd(2,6)=2$, $\gcd(2,10)=2$, so $2$ cannot be the answer. 100 * $\gcd(3,2)=1$, so the answer is $3$.