题解 | #kotori和素因子#

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<set>
#define INF 1e+7
using namespace std;
vector<int> Odd;
map<int,vector<int> > mp;
int ans = INF;
map<int,int> visited;
void Isprime(){
    bool flag;
    Odd.push_back(2);
    for(int i = 3;i <= 1000;++i){
        flag = true;
        for(int j = 2;j * j <= i;++j){
            if(i % j == 0){
                flag = false;
                break;
            }
        }
        if(flag)
            Odd.push_back(i);
    }
}
void dfs(int num,int sum,int n){
    if(num == n){
        ans = min(ans,sum);
        return;
    }
    for(int i = 0;i < mp[num].size();++i){
        if(!visited[mp[num][i]]){
            visited[mp[num][i]] = 1;
            dfs(num + 1,sum + mp[num][i],n);
            visited[mp[num][i]] = 0;
        }
    }
}
int main()
{
    int n,val;
    Isprime();
    cin >> n;
    for(int j = 0;j < n;++j){
        cin>> val;
        for(int i = 0;i < Odd.size() && Odd[i] <= val;){
            if(val % Odd[i] == 0){
                val /= Odd[i];
                mp[j].push_back(Odd[i]);
                if(visited.find(Odd[i]) == visited.end())
                    visited[Odd[i]] = 0;
            }
            else
                ++i;
        }
    }
    dfs(0,0,n);
    cout << (ans == INF ? -1 : ans);
}