题解 | kotori和素因子

解题思路

对每个数分解质因数
用 $\text{DFS}$ 尝试每个数选择不同的质因数
记录已使用的质因数，避免重复使用
当选择完所有数时，更新最小和

代码

c++
java
python

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

vector<int> getPrimeFactors(int n) {
    vector<int> factors;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            while(n % i == 0) n /= i;
            factors.push_back(i);
        }
    }
    if(n > 1) factors.push_back(n);
    return factors;
}

int ans = 1e9;
void dfs(vector<vector<int>>& factors, vector<bool>& used, int pos, int sum) {
    if(pos == factors.size()) {
        ans = min(ans, sum);
        return;
    }
    
    for(int prime : factors[pos]) {
        if(!used[prime]) {
            used[prime] = true;
            dfs(factors, used, pos + 1, sum + prime);
            used[prime] = false;
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];
    
    // 获取每个数的素因子
    vector<vector<int>> factors;
    for(int num : nums) {
        factors.push_back(getPrimeFactors(num));
    }
    
    vector<bool> used(1001, false);
    dfs(factors, used, 0, 0);
    
    cout << (ans == (int)1e9 ? -1 : ans) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static int ans = Integer.MAX_VALUE;
    
    static List<Integer> getPrimeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                while(n % i == 0) n /= i;
                factors.add(i);
            }
        }
        if(n > 1) factors.add(n);
        return factors;
    }
    
    static void dfs(List<List<Integer>> factors, boolean[] used, int pos, int sum) {
        if(pos == factors.size()) {
            ans = Math.min(ans, sum);
            return;
        }
        
        for(int prime : factors.get(pos)) {
            if(!used[prime]) {
                used[prime] = true;
                dfs(factors, used, pos + 1, sum + prime);
                used[prime] = false;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) nums[i] = sc.nextInt();
        
        // 获取每个数的素因子
        List<List<Integer>> factors = new ArrayList<>();
        for(int num : nums) {
            factors.add(getPrimeFactors(num));
        }
        
        boolean[] used = new boolean[1001];
        dfs(factors, used, 0, 0);
        
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
}


def get_prime_factors(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            factors.append(i)
        i += 1
    if n > 1:
        factors.append(n)
    return factors

def dfs(factors, used, pos, sum_val):
    global ans
    if pos == len(factors):
        ans = min(ans, sum_val)
        return
    
    for prime in factors[pos]:
        if not used[prime]:
            used[prime] = True
            dfs(factors, used, pos + 1, sum_val + prime)
            used[prime] = False

# 读入数据
n = int(input())
nums = list(map(int, input().split()))

# 获取每个数的素因子
factors = []
for num in nums:
    factors.append(get_prime_factors(num))

# DFS求解
ans = float('inf')
used = [False] * 1001
dfs(factors, used, 0, 0)

print(-1 if ans == float('inf') else ans)