CF 2013 E

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();
}
};

原文地址：https://blog.csdn.net/Antonio915/article/details/142719704

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！