题解 | #kotori和素因子#

#include<iostream>
#include<unordered_set>
#include<stack>
#include<vector>
using namespace std;

int n;
int a[1010];
int mi = 1e9, temp = 0;
unordered_set<int> s;
stack<int> f;
vector<vector<int>> h;

bool primer(int x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

void findi(int& x, int& i) {
    if (x < n - 1) {
        if(s.count(h[x][i])){
            ++i;
        }
        else if (i < h[x].size()) {
            f.push(i);
            s.insert(h[x][i]);
            temp += h[x][i];
            i = 0;
            ++x;  //深度遍历
        } else {
            if (!f.empty()) {
                i = f.top() + 1;
                s.erase(h[x-1][f.top()]);
                temp -= h[x-1][f.top()];
                f.pop();
            }
            --x;//到底回溯
        }
    } else {
        if(s.count(h[x][i])){
            ++i;
        }
        else if (i < h[x].size()-1) {
            temp += h[x][i];
            mi = min(mi, temp);
            temp -= h[x][i];
            ++i;
        } else {
            if (i == h[x].size()-1) {
                temp += h[x][i];
                mi = min(mi, temp);
                temp -= h[x][i];
            }
            i = f.top() + 1;
            temp -= h[x-1][f.top()];
            s.erase(h[x-1][f.top()]);
            f.pop();
            --x;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    for(int i=0;i<n;++i){
        h.push_back(vector<int>());
        for(int j=2;j<=a[i];++j){
            if(primer(j)&&(a[i]%j)==0)
                h[i].push_back(j);
        }
    }
    int x = 0, i = 0;
    while (1) {
        findi(x, i);
        if (x <= 0 && i >= h[0].size()) break;
    }
    if (mi == 1e9) printf("%d", -1);
    else printf("%d", mi);
    return 0;
}