2025.05.22-携程春招机考真题解析-第二题

📌 点击直达笔试专栏 👉《大厂笔试突围》

💻 春秋招笔试突围在线OJ 👉 笔试突围OJ

02. A先生的数组优化系统

问题描述

A先生负责一个数据处理系统，他需要对输入的数组进行优化处理。系统允许执行一种特殊的"协调操作"：选择数组中的任意两个元素，将它们替换为两个新的正整数，但要求这两个新整数的最大公约数必须等于原来两个元素的最大公约数。

A先生的目标是通过多次协调操作，使得数组所有元素的总和达到最小值。他想知道，经过任意次优化操作后，数组元素总和的最小可能值是多少。

输入格式

第一行包含一个正整数 $T$（$1\le T\le 10^4$），表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个正整数 $n$（$1\le n\le 2\times 10^5$），表示数组的长度。
• 第二行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n$（$1\le a_i\le 10^9$），表示数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示经过优化后能够得到的最小数组元素总和。

样例输入

2
2
1 2
3
3 7 9

样例输出

2
3

数据范围

• $1\le T\le 10^4$
• $1\le n\le 2\times 10^5$
• $1\le a_i\le 10^9$
• 所有测试用例中 $n$ 的总和不超过 $2\times 10^5$

题解

这道题的关键insight是理解协调操作的本质。当我们选择两个元素 $a_i$ 和 $a_j$，将它们替换为 $x$ 和 $y$，且要求 $\gcd (x,y)=\gcd (a_i,a_j)$ 时，我们可以选择 $x=y=\gcd (a_i,a_j)$。

通过多次这样的操作，我们可以将整个数组的所有元素都变成数组全体元素的最大公约数。具体分析：

1. 任意两个元素都可以被替换为它们的最大公约数
2. 通过连续的操作，所有元素最终都能变成整个数组的最大公约数
3. 因此最小总和就是 $n\times \gcd (a_1,a_2,\dots ,a_n)$

算法步骤：

1. 计算数组所有元素的最大公约数
2. 返回 $n$ 乘以这个最大公约数

时间复杂度为 $O(n\log A)$，其中 $A$ 是数组元素的最大值。

参考代码

• Python

import sys
import math
input = lambda: sys.stdin.readline().strip()

def gcd_list(arr):
    # 计算数组所有元素的最大公约数
    result = arr[0]
    for i in range(1, len(arr)):
        result = math.gcd(result, arr[i])
    return result

t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 计算最小总和
    g = gcd_list(arr)
    print(n * g)

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

ll gcd_func(ll a, ll b) {
    // 计算两个数的最大公约数
    return b == 0 ? a : gcd_func(b, a % b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ll g;
        cin >> g;
        
        // 计算所有元素的最大公约数
        for (int i = 1; i < n; i++) {
            ll x;
            cin >> x;
            g = gcd_func(g, x);
        }
        
        cout << g * n << endl;
    }
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    // 计算两个数的最大公约数
    private static long gcdFunc(long a, long b) {
        return b == 0 ? a : gcdFunc(b, a % b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            long g = sc.nextLong();
            
            // 计算所有元素的最大公约数
            for (int i = 1; i < n; i++) {
                long x = sc.nextLong();
                g = gcdFunc(g, x);
            }
            
            System.out.println(g * n);
        }
        sc.close();
    }
}