题解 | kotori和素因子

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1000;
bool isPrime[MAXV + 1];
vector<int> primes;

void init() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= MAXV; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= MAXV; j += i)
                isPrime[j] = false;
        }
    }
}

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

    vector<vector<int>> fac(n);
    for (int i = 0; i < n; ++i) {
        int x = a[i];
        for (int p : primes) {
            if (p * p > x) break;
            if (x % p == 0) {
                fac[i].push_back(p);
                while (x % p == 0) x /= p;
            }
        }
        if (x > 1) fac[i].push_back(x);
    }

    int best = 1e9;
    vector<bool> used(MAXV + 1, false);

    function<void(int, int)> dfs = [&](int idx, int sum) {
        if (sum >= best) return;
        if (idx == n) {
            best = sum;
            return;
        }
        for (int p : fac[idx]) {
            if (!used[p]) {
                used[p] = true;
                dfs(idx + 1, sum + p);
                used[p] = false;
            }
        }
    };

    dfs(0, 0);
    if (best == 1e9) cout << -1 << '\n';
    else cout << best << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();
    
    solve();
    return 0;
}