题解 | #kotori和素因子#

kotori和素因子

https://www.nowcoder.com/practice/7b1c858a3e7a41ed8364178979eaae67

题目链接

kotori和素因子

题目描述

kotori 拿到 $n$ 个互不相同的正整数 $a_1, a_2, \dots, a_n$ 。她要从每个 $a_i$ 中选出一个素因子 $p_i$ ，要求所有选出的素因子两两不同，即 $p_i \neq p_j$ ( $i \neq j$ )。

若无法满足要求输出 $-1$ ；否则输出所有选出的素因子之和 $\sum_{i=1}^{n} p_i$ 的最小可能值。

解题思路

本题要求为 $n$ 个不同的数分别选择一个唯一的素因子，并使得这些素因子的总和最小。

由于数据规模 $n$ 非常小（ $1 \le n \le 10$ ），这提示我们可以使用搜索算法来解决。一个经典的方法是深度优先搜索（DFS）配合回溯。

具体思路如下：

预处理：对输入的每个数 $a_i$ ，分解质因数，得到它所有不重复的素因子列表。因为 $a_i \le 1000$ ，我们可以用试除法高效地完成这一步。
深度优先搜索：我们定义一个递归函数 dfs(index, current_sum)，表示当前正在为第 index 个数（即 $a_{index}$ ）选择素因子，而已选择的素因子总和为 current_sum。
- 在函数中，我们遍历 $a_{index}$ 的所有素因子。对于其中一个素因子 $p$ ，如果它之前没有被选过，我们就选择它。
- 选择 $p$ 后，我们将其标记为“已使用”，然后递归调用 dfs(index + 1, current_sum + p)，继续为下一个数选择素因子。
- 当 dfs(index + 1, ...) 返回后，我们需要取消对 $p$ 的“已使用”标记，这个过程称为“回溯”。这使得其它的搜索分支可以继续使用 $p$ 。
递归出口：当 index 等于 $n$ 时，说明我们已经成功地为所有 $n$ 个数都选择了一个唯一的素因子。此时，我们得到了一个可行的解，其素因子之和为 current_sum。我们用这个和来更新全局的最小总和。
最优性剪枝：在搜索过程中，如果当前的 current_sum 已经大于或等于已找到的最小总和 min_sum，那么这条搜索路径不可能产生更优的解。我们可以提前终止这条路径的搜索，这被称为最优性剪枝。
最终结果：初始时，将最小总和 min_sum 初始化为一个极大值（或一个特殊标记，如 $-1$ ）。在整个搜索结束后，如果 min_sum 仍然是初始值，说明没有找到任何可行的方案，输出 $-1$ 。否则，输出 min_sum。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>

using namespace std;

int n;
vector<vector<int>> prime_factors;
long long min_sum = -1;
bool used_primes[1001] = {false}; // a_i <= 1000，素因子不会超过 1000

// 获取一个数的所有唯一素因子
vector<int> get_prime_factors(int num) {
    set<int> factors;
    int temp = num;
    for (int i = 2; i * i <= temp; ++i) {
        if (temp % i == 0) {
            factors.insert(i);
            while (temp % i == 0) {
                temp /= i;
            }
        }
    }
    if (temp > 1) {
        factors.insert(temp);
    }
    return vector<int>(factors.begin(), factors.end());
}

// index: 当前处理的数的下标
// current_sum: 当前已选素因子的和
void dfs(int index, long long current_sum) {
    // 递归出口：成功为所有 n 个数匹配了素因子
    if (index == n) {
        if (min_sum == -1 || current_sum < min_sum) {
            min_sum = current_sum;
        }
        return;
    }

    // 最优性剪枝
    if (min_sum != -1 && current_sum >= min_sum) {
        return;
    }

    // 遍历当前数的所有素因子
    for (int p : prime_factors[index]) {
        if (!used_primes[p]) {
            used_primes[p] = true; // 标记为已使用
            dfs(index + 1, current_sum + p);
            used_primes[p] = false; // 回溯，取消标记
        }
    }
}

int main() {
    cin >> n;
    prime_factors.resize(n);
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        prime_factors[i] = get_prime_factors(val);
    }

    dfs(0, 0);

    cout << min_sum << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collections;

public class Main {
    static int n;
    static ArrayList<ArrayList<Integer>> primeFactors;
    static long minSum = -1;
    static boolean[] usedPrimes = new boolean[1001]; // a_i <= 1000，素因子不会超过 1000

    // 获取一个数的所有唯一素因子
    static ArrayList<Integer> getPrimeFactors(int num) {
        Set<Integer> factors = new HashSet<>();
        int temp = num;
        for (int i = 2; i * i <= temp; ++i) {
            if (temp % i == 0) {
                factors.add(i);
                while (temp % i == 0) {
                    temp /= i;
                }
            }
        }
        if (temp > 1) {
            factors.add(temp);
        }
        ArrayList<Integer> factorList = new ArrayList<>(factors);
        return factorList;
    }

    // index: 当前处理的数的下标
    // currentSum: 当前已选素因子的和
    static void dfs(int index, long currentSum) {
        // 递归出口：成功为所有 n 个数匹配了素因子
        if (index == n) {
            if (minSum == -1 || currentSum < minSum) {
                minSum = currentSum;
            }
            return;
        }

        // 最优性剪枝
        if (minSum != -1 && currentSum >= minSum) {
            return;
        }

        // 遍历当前数的所有素因子
        for (int p : primeFactors.get(index)) {
            if (!usedPrimes[p]) {
                usedPrimes[p] = true; // 标记为已使用
                dfs(index + 1, currentSum + p);
                usedPrimes[p] = false; // 回溯，取消标记
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        primeFactors = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            primeFactors.add(getPrimeFactors(val));
        }

        dfs(0, 0);

        System.out.println(minSum);
    }
}

import sys

# 全局变量，用于在递归中传递状态
min_sum = -1
used_primes = []
prime_factors_list = []
n = 0

def get_prime_factors(num):
    """获取一个数的所有唯一素因子"""
    factors = set()
    temp = num
    i = 2
    while i * i <= temp:
        if temp % i == 0:
            factors.add(i)
            while temp % i == 0:
                temp //= i
        i += 1
    if temp > 1:
        factors.add(temp)
    return list(factors)

def dfs(index, current_sum):
    """
    index: 当前处理的数的下标
    current_sum: 当前已选素因子的和
    """
    global min_sum
    
    # 递归出口：成功为所有 n 个数匹配了素因子
    if index == n:
        if min_sum == -1 or current_sum < min_sum:
            min_sum = current_sum
        return

    # 最优性剪枝
    if min_sum != -1 and current_sum >= min_sum:
        return

    # 遍历当前数的所有素因子
    for p in prime_factors_list[index]:
        if not used_primes[p]:
            used_primes[p] = True # 标记为已使用
            dfs(index + 1, current_sum + p)
            used_primes[p] = False # 回溯，取消标记

# 主逻辑
n = int(input())
nums = list(map(int, input().split()))

prime_factors_list = [get_prime_factors(num) for num in nums]
used_primes = [False] * 1001
min_sum = -1
    
dfs(0, 0)
    
print(min_sum)

算法及复杂度

算法：深度优先搜索 (DFS) + 回溯
时间复杂度：预处理所有数字的质因数需要 $\mathcal{O}(n \cdot \sqrt{\max(a_i)})$ 。搜索部分，在最坏情况下，需要探索所有可能的匹配，复杂度是指数级的，大致为 $\mathcal{O}(n! \cdot k)$ ，其中 $k$ 是单个数字平均的素因子个数。由于 $n$ 很小，这个复杂度是可以接受的。
空间复杂度： $\mathcal{O}(n + \max(a_i))$ ，主要用于存储每个数的素因子列表、递归调用栈（深度为 $n$ ）以及标记素因子是否被使用的数组。