题目内容

给定一个长度为n的数组{$a_1, a_2, …, a_n$}，定义数组的权值为数组所有元素之和。你可以执行任意次以下操作，以使数组权值最小化：

• 选择两个索引 $i$ 和 $j$ ；
• 任意选取两个正整数 $x$ 和 $y$ ，但需满足 $gcd(x, y) = gcd(a_i, a_j)$；

题解

题面描述

给定一个长度为 $n$ 的数组 $\{a_1, a_2, \dots, a_n\}$，定义数组的权值为数组所有元素之和。你可以执行任意次以下操作，以使数组权值最小化：

• 选择两个索引 $i$ 和 $j$；
• 任意选取两个正整数 $x$ 和 $y$，但需满足$$\gcd(x, y) = \gcd(a_i, a_j);$$
• 将 $a_i \leftarrow x$，$a_j \leftarrow y$。