← 返回题目列表

Codeforces · 2013/E

E. 前缀 GCD

中文机器翻译题面 查看原题

由于曼苏尔厌倦了制作传奇,因此该任务将不再有传奇。

给定一个正整数数组 $$$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)$$$ 表示最大公约数 (GCD) $$$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$$$。

输出

对于每个测试用例,在单独的行上输出一个数字 - 问题的答案。

示例

输入 #1

5
3
4 2 2
2
6 3
3
10 15 6
5
6 42 12 52 20
4
42 154 231 66

输出 #1

6
6
9
14
51

注意

在第一个测试用例中,元素可以重新排列如下:$$$[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$$$。