题解 | #kotori和素因子#

挺有意思的一道题

#include<bits/stdc++.h>
using namespace std;
int a[1000],cnt,ans=0x3f3f3f3f;
vector<int> s[1100];
map<int,bool> mp;
bool is_Prime(int x){
    if(x==2||x==3)return true;
    if(x%6!=1&&x%6!=5)return false;
    for(int i=5;i<=sqrt(x);i+=6){
        if(!(x%i)||!(x%(i+2)))return false;
    }return true;
}
void dfs(int num,int n,int sum){
    if(num==n){
        ans=min(ans,sum);
    }
    for(int i=0;i<s[num].size();i++){
        if(!mp[s[num][i]]){
            mp[s[num][i]]=true;
            dfs(num+1,n,sum+s[num][i]);
            mp[s[num][i]]=false;
        }

    }
}
int main(){
    for(int i=2;i<=1000;i++)
        if(is_Prime(i))
                a[cnt++]=i;
    a[cnt]=0x3f3f3f3f;
    int n,i=0;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        int j=0;
        while(a[j]<=x){
            if(x%a[j]==0){
                s[i].push_back(a[j]);
            }
            j++;
        }
    }
    //int num=0;
    dfs(0,n,0);
    if(ans==0x3f3f3f3f)cout<<-1;
    else
    cout<<ans;        

}