˚‧º·(˚ ˃̣̣̥᷄⌓˂̣̣̥᷅ )‧º·˚

首先这道题数据范围很小，最多只有10个数，而且最大就1000。1000以内的数质因子最多的就4个(这个大家可以自己写个代码求一下或者打个表观察)

考虑暴力。 将每个数的所有质因子求出，分别存到对应的集合里面，每个集合分别取一个数算出所有满足条件的组合的和。

直接用dfs求出所有满足条件的组合的值更新最小即可。 时间复杂度为每个集合元素个数的乘积。

code：

#include<bits/stdc++.h>
using namespace std;

int e[10][10]; //第一维表示第几个数,第二维存这个数的质因子
int num[10]; //每个数的质因子的个数

int n;
int res = 1e9; //答案初始化为一个极大值,若没有更新则说明无法满足条件输出-1即可
bool vis[1001]; 
int a[15]; 

bool check(int x) {   //判断是否为质数
    if(x <= 1) return false;
    for(int i = 2; i * i <= x; i++) {
        if(x % i == 0) return false;
    }
    return true;
}

void dfs(int u, int sum) { 
    if(u == n) {
        res = min(res, sum);
        return ;
    }
    for(int i = 0; i < num[u]; i++) {
        if(!vis[e[u][i]]) {
            vis[e[u][i]] = true;
            dfs(u + 1, sum + e[u][i]);
            vis[e[u][i]] = false;
        }
    }
}

//void solve() { 这一行没有注释哈，不加发不出来     
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {   
        for(int j = 1; j * j <= a[i]; j++) {
            if(a[i] % j == 0) {
                if(check(j)) e[i][num[i]++] = j;
                if(check(a[i] / j)) e[i][num[i]++] = a[i] / j;
            }
        }
    }
    dfs(0, 0);
    cout << (res == 1e9 ?  -1 : res) << "\n";
//} 这一行没有注释哈，不加发不出来

//signed main() { 这一行没有注释哈，不加发不出来
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) solve();
//} 这一行没有注释哈，不加发不出来