1742D.md (2000B)
1 Source: https://codeforces.com/problemset/problem/1742/D 2 3 D. Coprime 4 5 time limit per test 6 7 3 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 Given an array of $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$). Find the maximum value of $i + j$ such that $a_i$ and $a_j$ are coprime,$^{\dagger}$ or $-1$ if no such $i$, $j$ exist. 22 23 For example consider the array $[1, 3, 5, 2, 4, 7, 7]$. The maximum value of $i + j$ that can be obtained is $5 + 7$, since $a_5 = 4$ and $a_7 = 7$ are coprime. 24 25 $^{\dagger}$ Two integers $p$ and $q$ are [coprime](https://en.wikipedia.org/wiki/Coprime_integers) if the only positive integer that is a divisor of both of them is $1$ (that is, their [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) is $1$). 26 27 Input 28 29 The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10$) — the number of test cases. The description of the test cases follows. 30 31 The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot10^5$) — the length of the array. 32 33 The following line contains $n$ space-separated positive integers $a_1$, $a_2$,..., $a_n$ ($1 \leq a_i \leq 1000$) — the elements of the array. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$. 36 37 Output 38 39 For each test case, output a single integer — the maximum value of $i + j$ such that $i$ and $j$ satisfy the condition that $a_i$ and $a_j$ are coprime, or output $-1$ in case no $i$, $j$ satisfy the condition. 40 41 Example 42 43 Input 44 45 ``` 46 6 47 48 3 49 50 3 2 1 51 52 7 53 54 1 3 5 2 4 7 7 55 56 5 57 58 1 2 3 4 5 59 60 3 61 62 2 2 4 63 64 6 65 66 5 4 3 15 12 16 67 68 5 69 70 1 2 2 3 6 71 ``` 72 73 Output 74 75 ``` 76 6 77 12 78 9 79 -1 80 10 81 7 82 ``` 83 84 Note 85 86 For the first test case, we can choose $i = j = 3$, with sum of indices equal to $6$, since $1$ and $1$ are coprime. 87 88 For the second test case, we can choose $i = 7$ and $j = 5$, with sum of indices equal to $7 + 5 = 12$, since $7$ and $4$ are coprime.