https://ac.nowcoder.com/acm/problem/50042——(kotori和素因子)

题目：https://ac.nowcoder.com/acm/problem/50042
思路：将每个数的质因子求出来，然后进行dfs找寻答案，不用考虑最小是因为根据题意找出来必然就是最小答案。
代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<utility>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const LL mod=1e9+7;
int read() {
    char ch=getchar();int x=0,f=1;
    while(ch<'0' || ch>'9')    {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);}
LL fpow(LL a,LL b) {
    LL res=1;
    while(b) {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
vector<int> p[11];
int v[1005];
int ans=1e9+7;
void dfs(int n,int res) {
    if(res>=ans) return;
    if(!n) {
        ans=res;
    }
    else {
        for(int i=0;i<p[n].size();++i) {
            if(!v[p[n][i]]) {
                v[p[n][i]]=1;
                dfs(n-1,res+p[n][i]);
                v[p[n][i]]=0;
            }
        }
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
//    cout<<"Accepted!\n";
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        for(int j=2;j<=a/j;++j) {
            if(a%j==0) {
                p[i].push_back(j);
            }
            while(a%j==0) a/=j;
        }
        if(a>1) p[i].push_back(a);
    }
    dfs(n,0);
    if(ans==1e9+7) cout<<-1;
    else cout<<ans;
    return 0;
}