AcWing 1118. 分成互质组
原题链接
简单
作者:
小灯笼
,
2020-12-05 21:11:02
,
所有人可见
,
阅读 410
#include <iostream>
#include <vector>
using namespace std;
const int N = 13;
vector<int> group[N];
int a[N];
int n;
int res = 20;
int numGroup;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
bool ischecked(int i, int n)
{
for(int j = 0 ; j < group[i].size(); j ++)
{
if(gcd(n, group[i][j]) != 1) return false;
}
return true;
}
void dfs(int u)
{
if(u == n)
{
res = min(res, numGroup);
//cout<<"res "<<res<<endl;
return;
}
int item = a[u];
for(int i = 0; i < numGroup; i ++) //加入已有的组
{
if(ischecked(i, item))
{
//cout<<ischecked(i, item)<<endl;
group[i].push_back(item);
dfs(u + 1);
group[i].pop_back();
}
}
group[numGroup].push_back(item); //创建一个新组
numGroup += 1;
dfs(u + 1);
numGroup -= 1;
group[numGroup].pop_back();
}
int main()
{
cin>>n;
for(int i = 0; i < n; i++) cin>>a[i];
dfs(0);
cout<<res;
}