题解 | kotori和素因子

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

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> primes_list(n);
    vector<int> all_primes;
    for (int i = 0; i < n; ++i) {
        primes_list[i] = get_primes(a[i]);
        for (int p : primes_list[i]) {
            all_primes.push_back(p);
        }
    }

    sort(all_primes.begin(), all_primes.end());
    all_primes.erase(unique(all_primes.begin(), all_primes.end()), all_primes.end());

    int m = all_primes.size();
    vector<vector<int>> dp(m + 1, vector<int>(1 << n, INT_MAX));
    dp[0][0] = 0;

    for (int i = 0; i < m; ++i) {
        int p = all_primes[i];
        vector<int> bits;
        for (int j = 0; j < n; ++j) {
            for (int prime : primes_list[j]) {
                if (prime == p) {
                    bits.push_back(j);
                    break;
                }
            }
        }

        for (int mask = 0; mask < (1 << n); ++mask) {
            if (dp[i][mask] == INT_MAX) continue;

            dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][mask]);

            for (int j : bits) {
                if (!(mask & (1 << j))) {
                    int new_mask = mask | (1 << j);
                    dp[i + 1][new_mask] = min(dp[i + 1][new_mask], dp[i][mask] + p);
                }
            }
        }
    }

    int answer = dp[m][(1 << n) - 1];
    cout << (answer == INT_MAX ? -1 : answer) << endl;

    return 0;
}