题解 | kotori和素因子

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_set>
using namespace std;
// 素因子大概是质因数的意思
// n 不大
// 找出小于a最大值的所有质数
// 找出a中每个值的质因数
// 穷举
bool isBase(int v, const vector<int>& lst) {
    int q = int(ceil(sqrt(v))) +2;
    for(auto b : lst) {
        if(b >= q) {
            break;
        }
        if(v % b == 0) {
            return false;
        }
    }
    return true;
}
vector<int> GetBList(int v) {
    vector<int> all{2,3};
    for(auto i = 4; i <= v; i++) {
        if((i&1) == 0) {
            continue;
        }
        if(isBase(i, all)) {
            all.push_back(i);
        }
    }
    return all;
}
vector<int> GetFac(int v, const vector<int>& lst) {
    vector<int> fac;
    for(auto b : lst) {
        if(v%b == 0) {
            fac.push_back(b);
        }
    }
    return fac;
}
int sumMin = 1e9;
bool ok = false;

void Dfs(const vector<int>& lst, const vector<int>& a, int i, int sum, unordered_set<int>& used) {
    if(i == a.size()) {
        sumMin = min(sumMin,sum);
        ok = true;
        return;
    }
    auto fac = GetFac(a[i], lst);
    for(auto v : fac) {
        if(used.find(v) != used.end()) {
            continue;
        }
        used.insert(v);
        Dfs(lst, a, i+1, sum + v, used);
        used.erase(v);
    }
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int nMax = 0;
    for(auto& v : a) {
        cin >> v;
        nMax = max(v,nMax);
    }
    auto bLst = GetBList(nMax);
    unordered_set<int> used;
    Dfs(bLst, a, 0, 0, used);
    cout << (ok?sumMin:-1) << endl;
}
// 64 位输出请用 printf("%lld")