Codeforces Round #720 - 1521B. Nastia and a Good Array

This is an unofficial editorial for [Nastia and a Good Array](https://codeforces.com/contest/1521/problem/B). ## Problem Statement Nastia has received an array of n positive integers as a gift. She calls such an array a good that for all i ($ 2 <= i <= n $) takes place $ gcd(a_i − 1, a_i )$ = 1, where $ gcd(u, v) $ denotes the greatest common divisor (GCD) of integers u and v. You can perform the operation: select two different indices $i$, $j$ ($1 <= i, j <= n, i \neq j$) and two integers $x$, $y$ ($1 <= x,y <= 2 * 10^9$) so that $ min(a_i, a_j) = min(x, y)$. Then change $a_i$ to $x$ and $a_j$ to $y$. The girl asks you to make the array good using at most $n$ operations. It can be proven that this is always possible. ## Approach From the statement, we can have our first obversation which is $ a_i - 1 $ and $a_i$ are coprime, denoted by $ gcd(a_i − 1, a_i )$ = $1$. Two integers are coprime if the only positive integer that is a divisor of both of them is 1, mathematically $ gcd(a, b) = 1 $. Therefore, this question can be rephrased as "how to make a_i - 1 and a_i coprime using at most $n$ operations". ### Solution 1 We can use the fact that an integer $x$ and $ x \pm 1 $ are coprime. First let's find the min value $x$ and its position $pos$ in array $a$ as we have to use this value to perform the operations. For all integer $i$ where $ 1 <= i <= n $, we can perform $ (pos, i, x ,abs(pos - i)) $ to replace $a_i$ to $x$ + $abs(pos - i)$. For the first test case, we can make $ [9, 6, 3, 11, 15] $ to $ [5, 4, 3, 4, 5] $ using $ n - 1 $ operations. ### Solution 2 We can put a prime number, let's say $ 1e9 + 7$ on every odd index if the minimum value is on even index and vice versa. In this case, we just need $ (n + 1) / 2 $ operations to turn $ [9, 6, 3, 11, 15] $ to $ [9, 1e9 + 7, 3, 1e9 + 7, 15] $.