Codeforces Round #720 Nastia and a Good Array - 构造

题意

给你一个长度为$n$的数组$a$，要你通过以下方式替换$a$的值，使得对于任意$i$有gcd(a_{i - 1}, a_{i}) = 1：
选择一个满足$\min{(a_i, a_j)} = \min{(x, y)}$的$i$，$j$，$x$和$y$。然后将$a_i$替换为$x$，$a_j$替换为$y$。

题解

我们最多可以更换n个数，且新的数字的取值可以到$2\cdot 10^9$，那么我们索性将除了原数组中最小数以外的所有数都换成两个大素数：$10^9+7$和$10^9+9$即可。

代码