T175410 分成互质组
因为n很小，直接暴力枚举
两种状态：
1.放入桶中。如果当前数字可以放入某个桶中，放入。如果可以放入多个桶，先一个一个来，全部枚举。
注意：枚举完之后记得恢复现场
2.新开辟一个桶。如果不能放入，则开辟一个桶。如果可以放入，也可以选着不放入，再新开辟一个桶：防止遗留
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int ans=1e9,cnt;
int n,a[N];
vector<int> g[N];
int gcd(int y, int x) {
return x ? gcd(x, y % x) : y;
}
void dfs(int u) {
if (cnt >= ans) return;//剪枝，如果当前解比之前还大，说明已经不用继续了
if (u > n) {
ans = cnt;
return;
}
auto check = [](int x, int id) {//判断是否可以放入
for (auto v : g[x]) {
if (gcd(v, a[id]) > 1) {
return 0;
}
}
return 1;
};
for (int i = 0; i < cnt; i++) {
if (check(i,u)) {
g[i].push_back(a[u ]);
dfs(u + 1);
g[i].pop_back();//恢复现场
}
}
g[cnt++].push_back(a[u]);//无论能否放入都开辟一个新桶
dfs(u + 1);
g[--cnt].pop_back();
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(1);
cout << ans;
return 0;
}