codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.