题解思路

1. 最大组合粘合度

由于对于任意一个单独的粘合剂，其组合粘合度就是它本身，即
$\gcd(a_i) = a_i$, 因此在所有可能的组合中，取单个粘合剂的情况能够达到最大的粘合度。故所有组合中的最大组合粘合度为
$\max(a_1, a_2, \dots, a_n).$

2. 最小组合粘合度

另一方面，对于多个数，其 $\gcd$ 具有如下性质：

• 对于任意集合 $S$ 有
  $\gcd(S) \leq \min_{x \in S} x.$
• 当集合中的元素越多时，由于 $gcd$ 的单调性（增加新的数只可能使 $gcd$ 变小或保持不变），所有组合中最小的组合粘合度必定出现在选取所有粘合剂时，即
  $\gcd(a_1, a_2, \dots, a_n).$

复杂度分析

• 对于最大值，我们只需要遍历一次数组，时间复杂度是O(n)。
• 对于最小值，我们需要用$gcd$函数遍历所有粘合剂，时间复杂度是O(n)。
• 因此，整个算法的时间复杂度是O(n)，适合处理最大规模的输入。

代码实现

C++实现

#include <bits/stdc++.h>
using namespace std;

// 计算两个数的最大公因数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a);
}

int main() {
    int n;
    cin >> n;  // 读入粘合剂种数
    vector<int> a(n);  // 存储所有粘合剂的粘合度
    int min_gcd = 0, max_gcd = 0;
    
    // 读入粘合剂的粘合度，并计算最小值和最大值
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        min_gcd = gcd(min_gcd, a[i]);  // 计算所有粘合剂的最大公因数
        max_gcd = max(max_gcd, a[i]);  // 计算最大值
    }
    
    // 输出最小和最大粘合度
    cout << min_gcd << " " << max_gcd << endl;
    return 0;
}

Python实现

import math

# 主函数
def main():
    n = int(input())  # 读取粘合剂的数量
    a = list(map(int, input().split()))  # 读取所有粘合剂的粘合度

    min_gcd = a[0]
    max_gcd = a[0]

    # 遍历所有粘合剂，更新最小值和最大公因数
    for i in range(1, n):
        min_gcd = math.gcd(min_gcd, a[i])
        max_gcd = max(max_gcd, a[i])
    
    # 输出最小和最大粘合度
    print(min_gcd, max_gcd)

# 调用主函数
if __name__ == "__main__":
    main()

Java实现

import java.util.*;

public class Main {
    // 计算最大公因数
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a;
            a = b;
            b = temp % b;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 读取粘合剂的数量
        int[] a = new int[n];
        
        // 读取所有粘合剂的粘合度
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int min_gcd = a[0];
        int max_gcd = a[0];

        // 遍历所有粘合剂，更新最小值和最大公因数
        for (int i = 1; i < n; i++) {
            min_gcd = gcd(min_gcd, a[i]);
            max_gcd = Math.max(max_gcd, a[i]);
        }

        // 输出最小和最大粘合度
        System.out.println(min_gcd + " " + max_gcd);
    }
}

题目内容

小红有$n$种粘合剂，第$i$种粘合剂的粘合度为$a_4$。 他会从中挑选$k(1≤k≤n)$种粘合剂组合使用,记桃选的$k$种粘合剂依次为$a_{b_1},a_{b_2}...,a_{b_k},$，那么,组合粘合变为所选粘合剂初始粘合度的最大公因数$god(a_{b_1},a_{b_2},..,a_{b_k})$,当$k=1$时,此时组合粘合度为$a_{b_1}$

现在小红想询问搭配使用粘合剂的最低和最高粘合度为多少?

最大公因数，指两个整数共有约数中最大的一个。例如，$12$和$30$的公约数有$1,2,3,6$，其中最大的约数是$6$，因此$god(12,30) =6$。

输入描述

第一行一个整数$n(1≤n≤10^5)$,表示粘合剂种数。

第二行$n$个整数，第$i$个整数为$a_i(1≤a≤10^9)$,表示第$i$种粘合剂的粘合度。

输出描述

两个整数，以空格隔开，分别表示对一个物品任意搭配使用粘合剂的最低和最高粘合度。

样例1

输入

3
2 4 6

输出

2 6