解题思路
-
这是一个最小公倍数(LCM)问题,但有特殊要求:
- 需要从5个数中选择至少3个数
- 计算这些数的最小公倍数
- 在所有可能的组合中找出最小值
-
解题步骤:
- 使用组合的方式选择3、4或5个数
- 计算每种组合的最小公倍数
- 比较所有结果,取最小值
-
关键函数:
- 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)
- 空间复杂度:
- 需要存储选中的数字