AcWing 1118. 分成互质组---好理解版本
原题链接
简单
作者:
小.bug
,
2022-05-16 20:53:06
,
所有人可见
,
阅读 114
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int a[N];
int res = 15;
vector<int> group[N];
int n;
int gcd(int a,int b)
{
return b ? gcd(b, a % b) : a;
}
void dfs(int u, int cnt)
{
if(cnt >= res) return;
if(u > n)
{
res = cnt;
return;
}
//从当组里找
bool success = false;
for(int i = 0; i < cnt; i++)
{
bool flag = true;
for(int j = 0; j < group[i].size(); j++)
{
if(gcd(a[u],group[i][j]) > 1)
{
flag = 0;
break;
}
}
//找到了
if(flag)
{
success = true;
group[i].push_back(a[u]);
dfs(u + 1, cnt);
group[i].pop_back();
}
}
//一组都没找到
if(!success)
{
group[cnt].push_back(a[u]);
dfs(u+1,cnt+1);
//group[cnt].pop_back();
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
dfs(1,0);
cout << res << endl;
return 0;
}