codeforces-scrape

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

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.