题解 | kotori和素因子

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

int vis[400], minVal = 10000000000;
vector<set<int> > v;

set<int> resolve(int n) {
	//分解为素数并存vector
	set<int> s;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			s.insert(i);
			n /= i;
			i = 1;
		}
	}
	s.insert(n);
	return s;
}

//找不重复的素数之和 
void dfs(int deep, int ans) {
	if (deep == v.size() + 1) {
		minVal = min(minVal, ans);
		return;
	}
	set<int> s = v[deep - 1];
	for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
		int e = *it;
		if (!vis[e]) {
			vis[e] = 1;
			dfs(deep + 1, ans + e);
			vis[e] = 0;
		}
	}
}
//使用STL库
int main() {
	int t, result = -1;
	cin >> t;
	int len = t; 
	while(t-- > 0) {
		int n;
		cin >> n;
		set<int> ans = resolve(n);
		v.push_back(ans);
	}
	set<int> total;
	for (vector<set<int> >::iterator e = v.begin(); e != v.end(); e++) {
		total.insert(e -> begin(), e -> end());
	}
	if (total.size() >= len) {
		dfs(1, 0);
		result = minVal;	
	}
	cout << result << endl;
}