CF2013E Prefix GCD

由于 Mansur 厌倦了编写题目背景，这道题没有背景描述。 给定一个正整数数组 $a_1, a_2, \ldots, a_n$。你可以任意重新排列数组中的元素。你需要找到如下表达式的最小可能值： $$ \gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n) $$ 其中 $\gcd(a_1, a_2, \ldots, a_n)$ 表示 $a_1, a_2, \ldots, a_n$ 的最大公约数。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$），表示初始数组。 所有测试数据中 $n$ 的总和不超过 $10^5$。 所有测试数据中 $\max(a_1, a_2, \ldots, a_n)$ 的总和不超过 $10^5$。

对于每组测试数据，输出一个整数，表示该组数据的答案。每个答案占一行。

在第一个测试用例中，元素可以重新排列为 $[2, 4, 2]$。此时答案为 $\gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6$。 在第三个测试用例中，元素可以重新排列为 $[6, 10, 15]$。此时答案为 $\gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9$。 由 ChatGPT 4.1 翻译