E. Prefix GCD

#数论 #暴力 #贪心

题目描述

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,\dots ,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)+\dots +\gcd (a_1,a_2,\dots ,a_n),$$
where $\gcd (a_1,a_2,\dots ,a_n)$ denotes the greatest common divisor $(GCD)$ of $a_1,a_2,\dots ,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,\dots ,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,\dots ,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.

样例 #1

样例输入 #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

解法

解题思路

首先我们发现，前缀$gcd$一定是一个不递增的，并且前缀$gcd$一定只有$lo{g}_2$种。由于不递增这个性质，我们可以发现，如果我们第一个数字选择最小的一个数字，并且后面选的数与前面那个数的$gcd$也是最小的，那么这样构造的前缀$gcd$的和一定是最小的，即${\sum }_{i=1}^n{\sum }_{j=1}^{i}gcd(a_i,a_j)$最小。

贪心的正确性显然，因为无论如何都是不递增的，那么直接构造一个前部分递减，后部分全部都相等的序列，一定是$gcd$前缀和最小的。

由于只有$lo{g}_2$种$gcd$的结果，因此我们如果得到了最小的$gcd$结果后，就可以结束了，因为剩下的部分一定都是相等的一段，最后加上那一段的和即可。

代码

void solve() {int n;std::cin >> n;std::vector<int>a(n + 1);int g = 0;for (int i = 1; i <= n; ++i) {std::cin >> a[i];g = std::gcd(g, a[i]);}auto pos  = std::min_element(a.begin() + 1, a.end());std::vector<int>vis(n + 1);vis[pos - a.begin()] = 1;int now = *pos, cnt = 1, res = now;while (now > g) {++cnt;pii minx = { inf,inf };for (int i = 1; i <= n; ++i) {if (vis[i]) continue;auto& [min, idx] = minx;if (std::gcd(now, a[i]) < min) {min = std::gcd(now, a[i]);idx = i;}}auto [min, idx] = minx;vis[idx] = 1; now = min;res += now;}res += (n - cnt) * g;std::cout << res << "\n";}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;while (t--) {solve();}
};