Codeforces Round 973 (Div. 2) |
---|
Finished |
Since Mansur is tired of making legends, there will be no legends for this task.
You are given an array of positive integer numbers $$$a_1, a_2, \ldots, a_n$$$. The elements of the array can be rearranged in any order. You need to find the smallest possible value of the expression $$$$$$\gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n),$$$$$$ where $$$\gcd(a_1, a_2, \ldots, a_n)$$$ denotes the greatest common divisor (GCD) of $$$a_1, a_2, \ldots, a_n$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains a single number $$$n$$$ ($$$1 \le n \le 10^5$$$) — the size of the array.
The second line of each test case contains $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the initial array.
The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
The sum of $$$\max(a_1, a_2, \ldots, a_n)$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, output a single number on a separate line — the answer to the problem.
534 2 226 3310 15 656 42 12 52 20442 154 231 66
6 6 9 14 51
In the first test case, the elements can be rearranged as follows: $$$[2, 4, 2]$$$. Then the answer will be $$$\gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6$$$.
In the third test case, the elements can be rearranged as follows: $$$[6, 10, 15]$$$. Then the answer will be $$$\gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9$$$.
Name |
---|