题解 | #kotori和素因子#

题干要求计算素因子的和，n个数，每个数都可能有若干个素因子，选择当前数的素因子相当于一次分叉，那么选择过程形成一个多叉树，最后一个数的素因子选择后，相当于到达多叉树的叶子，此时计算所有素因子的和。

想要遍历所有可能的和，就需要使用深度优先遍历dfs的方法遍历整个多叉树，最后能得出最小的和。

#include <climits>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

//检查素因子
bool isPrimer(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

//查找factors中是否有p，i表示factors中的元素个数
bool has(vector<int> &factors,int i,int p){
    for(int j=0;j<i;j++){
        if(factors[j]==p)
            return true;
    }
    return false;
}

//深度遍历函数，
void dfs(vector<int> &arr,vector<int> &factors,int i,int &res){
    //表示遍历完所有数
    if(i==arr.size()){
        int all=0;
        for(int j=0;j<i;j++){
            all+=factors[j];
        }
        //如果res小于因子和，则更新
        if(res>all){
            res=all;
        }
        return;
    }
    //遍历查找当前数的所有合法素因子
    for(int j=2;j<=arr[i];j++){
        //j是素数，且是因子，且不重复
        if(isPrimer(j) && arr[i]%j==0 && !has(factors, i, j)){
            //覆盖当前素因子
            factors[i]=j;
            //递归调用
            dfs(arr,factors,i+1,res);
        }
    }
    //此处返回表示当前元素无合法素因子，res不会更新
}

int main() {
    int num;
    cin>>num;
    vector<int> arr(num,0);

    for(int i=0;i<num;i++){
        cin>>arr[i];
    }

    //存储因子
    vector<int> factors(num,0);
    //存储结果
    int res=INT_MAX;
    dfs(arr,factors,0,res);

    if(res==INT_MAX){
        cout<<-1;
    }else {
        cout<<res;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")