解题代码
回溯算法
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
inline int gcd(int a,int b) {
return b? gcd(b, a%b):a;
}
int n;
// int groupCnt;
// int g[N][N];
int a[N];
// bool used[N];
int res = N;
vector<vector<int>> groups = {};
void dfs(int cur) {
if((int)groups.size() > res) return;
if(cur >=n) {
res = min(res, (int)groups.size());
return;
}
int curLen = groups.size();
int v = a[cur];
// bool put1 = true;
for(int i=0;i<curLen;++i) {
bool ok = true;
for(int u: groups[i]) {
if(gcd(u,v) > 1) {
//不互质
ok = false;
break;
}
}
if(ok) {
//如果 v 和 这个组内所有的数都是互质的话,就可以加入这个组
groups[i].push_back(v);
dfs(cur+1);
//回溯,去试试放入别的组
groups[i].pop_back();
// put1 = false;
}
}
// if(put1) {
//额外放到一个集合里面
//v 自己作为一个组,等其他组加入
groups.push_back({v});
dfs(cur+1);
groups.pop_back();
// }
}
int main()
{
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i];
dfs(0);
cout << res <<endl;
return 0;
}