题意简述
Vanya 有一个包含 $n$ 个顶点的图（顶点编号从 $1$ 到 $n$），以及一个包含 $n$ 个整数的数组 $a$；最初图中没有边。Vanya 感到无聊，为了娱乐，他决定进行 $n - 1$ 次操作。
第 $x$ 次操作（操作从 $1$ 开始编号）如下：
- 选择两个不同的数字 $1 \leq u, v \leq n$，使得 $|a_u - a_v|$ 被 $x$ 整除。
- 在顶点 $u$ 和 $v$ 之间添加一条无向边。
帮助 Vanya 使用这 $n - 1$ 次操作来构建一个连通图，或者判断这是不可能的。
思路分析
显而易见，较大的数更不容易被整除，所以我们可以从大到小枚举 $x$。
这个 $x$ 满足存在一对 $u,v$，使得 $|a_u - a_v|$ 被 $x$ 整除，即 $|a_u - a_v| \bmod x = 0$。
我们还知道 $(a + b) \bmod c = ((a \bmod c) + (b \bmod c)) \bmod c$，
所以上述条件可以进一步简化为 $a_u \equiv a_v \pmod{x}$。
这个式子将枚举两点权值差的 $O(n^2)$ 优化到了求权值模后找权值模相等的对应两点的 $O(n)$ 。
如果存在两点的权值模相等，那么我们检查这两点是否已经连通。如果尚未连通，则在它们之间连一条边。
接下来我们证明，对于每一个 $x$，至少存在一组相等的 $u,v$ 使得 $a_u \equiv a_v \pmod{x}$。
处理每一个 $x$ 时，图中还剩下 $x$ 条边需要被连接，还有 $x+1$ 个连通块。
我们需要在某两个连通块之间添加一条边。
$x+1$ 个连通块中至少存在 $x+1$ 个两两不在同一连通块内的点。
根据 鸽巢原理，$x+1$ 个数在模 $x$ 的情况下必定存在至少两个数，它们的取余结果相同。
因此，一定存在至少一种方案满足题意。
代码实现
见 274562589。