解题思路

  1. 这是一个最小公倍数(LCM)问题,但有特殊要求:

    • 需要从5个数中选择至少3个数
    • 计算这些数的最小公倍数
    • 在所有可能的组合中找出最小值
  2. 解题步骤:

    • 使用组合的方式选择3、4或5个数
    • 计算每种组合的最小公倍数
    • 比较所有结果,取最小值
  3. 关键函数:

    • GCD(最大公约数):辗转相除法
    • LCM(最小公倍数):两数相乘除以最大公约数

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 计算最大公约数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算最小公倍数
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

// 计算多个数的最小公倍数
long long getLCM(vector<int>& nums) {
    long long result = nums[0];
    for(int i = 1; i < nums.size(); i++) {
        result = lcm(result, nums[i]);
    }
    return result;
}

int main() {
    vector<int> nums(5);
    for(int i = 0; i < 5; i++) {
        cin >> nums[i];
    }
    
    long long minLCM = LLONG_MAX;
    
    // 遍历所有可能的组合
    for(int i = 0; i < 32; i++) {
        if(__builtin_popcount(i) >= 3) {  // 至少选3个数
            vector<int> selected;
            for(int j = 0; j < 5; j++) {
                if(i & (1 << j)) {
                    selected.push_back(nums[j]);
                }
            }
            minLCM = min(minLCM, getLCM(selected));
        }
    }
    
    cout << minLCM << endl;
    return 0;
}
import java.util.*;

public class Main {
    // 计算最大公约数
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 计算最小公倍数
    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
    
    // 计算多个数的最小公倍数
    static long getLCM(List<Integer> nums) {
        long result = nums.get(0);
        for(int i = 1; i < nums.size(); i++) {
            result = lcm(result, nums.get(i));
        }
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = new int[5];
        for(int i = 0; i < 5; i++) {
            nums[i] = sc.nextInt();
        }
        
        long minLCM = Long.MAX_VALUE;
        
        // 遍历所有可能的组合
        for(int i = 0; i < 32; i++) {
            if(Integer.bitCount(i) >= 3) {  // 至少选3个数
                List<Integer> selected = new ArrayList<>();
                for(int j = 0; j < 5; j++) {
                    if((i & (1 << j)) != 0) {
                        selected.add(nums[j]);
                    }
                }
                minLCM = Math.min(minLCM, getLCM(selected));
            }
        }
        
        System.out.println(minLCM);
    }
}
from itertools import combinations

def gcd(a, b):
    """计算最大公约数"""
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    """计算最小公倍数"""
    return a * b // gcd(a, b)

def get_lcm(nums):
    """计算多个数的最小公倍数"""
    result = nums[0]
    for i in range(1, len(nums)):
        result = lcm(result, nums[i])
    return result

# 读取输入
nums = list(map(int, input().split()))

# 计算所有可能组合的最小公倍数
min_lcm = float('inf')
for i in range(3, 6):  # 选择3到5个数
    for comb in combinations(nums, i):
        min_lcm = min(min_lcm, get_lcm(list(comb)))

print(min_lcm)

算法及复杂度

  • 算法:枚举组合 + GCD/LCM计算
  • 时间复杂度: - 为数字个数(这里是5)
  • 空间复杂度: - 需要存储选中的数字