首页 > 试题广场 >

小红的gcd

[编程题]小红的gcd

热度指数：1211 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红有一个长度为 $n$ 的数组，她希望数组元素之和越少越好。
她可以进行任意次操作，每次选择数组中的两个元素 $a_i$ 和 $a_j$ ，令 $a_i=a_j=\gcd(a_i,a_j)$ 。
所有操作结束后，请你输出最小的数组元素之和。

输入描述:

第一行有一个整数  。
第二行有  个整数  。

输出描述:

输出一个整数，代表最小的数组元素之和 。

示例1

输入

5
2 4 6 8 10

输出

算法知识视频讲解

牛客203596504号

实际上这道题暴力也能过，挨个求gcd别回头就行。但用上贪心可能更快点：

首先，由于gcd一定不超过两个数中最小的那个，所以数列最终会变成同一个数。
既然要贪心，我们肯定选择最小值来求gcd，这样下降更快。
求gcd的结果只有三种：
1. 整除。它会变得跟最小值相同，既然如此，现在就可以把它剔除出去了。
2. 互质。而1与任何数的gcd都是1，整个数列都会变1，恭喜你可以直接输出答案了。
3.其他。那么gcd一定比最小值更小，它就会成为新的最小值！重新遍历。

int n = read_uint();
int min = 0;
for (int i = 0; i < n; i++) {
    a[i] = read_uint();
    if (a[i] < a[min]) min = i; // 找到最小值
}
for (int i = 0; i < n; i++) {
    if (i == min || a[i] == 0) continue;
    a[i] %= a[min]; // 整除。那么gcd等于a[min]，直接剔除重复的a[i]
    if (a[i] == 0) continue; // 值为0将不再参与任何运算
    a[i] = gcd(a[i], a[min]);
    if (a[i] == 1) { // 互质
        write_uint(n); // 直接输出答案
        putchar('\n');
        return 0;
    } else { // 只要不整除，gcd一定小于a[min]
        a[min] = 0; // 按照规则，a[min]也会变成gcd，剔除掉重复的a[min]
        min = i; // 所以它成为新的最小值
        i = -1; // 从头开始遍历
    }
}
write_ulong((long)n * a[min]); // 注意乘积超出了int范围
putchar('\n');

发表于 2026-01-30 03:29:09 回复(0)