目录
每次选择一个数进入所分好的组，比较这个数与分组中每个数是否互质，互质则进入此分组，否则新开辟一个分组
int main ()
{
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
dfs(1,0,0,0);
cout<<res<<endl;
return 0;
}u -> 第几组
v -> 第几组中的第几个数
w -> 我用了多少个数
x -> 当前从哪个序列编号开始找下一个互质的数放入组中
void dfs(int u,int v,int w,int x) // 递归指数型枚举
{
if(u>=res) return ;
if(w==n)
{
res=u;
return ;
}
bool flag=1;
for(int i=x;i<n;i++)
if(!st[i] && check(u,v,i))
{
group[u][v]=i;
st[i]=1;
flag=0;
dfs(u,v+1,w+1,i+1);
st[i]=0;
}
if(flag) dfs(u+1,0,w,0);
}我们此时的flag变量即标记是否互质变量，初始值赋值为1，如果被选了则被赋值为0，没被选则还是1，此时我们就要新开辟一个分组，因为这个数与其他分组中的数不互质，不符合题目要求。
bool check(int u,int v,int i)
{
for(int j=0;j<v;j++)
{
if(gcd(p[group[u][j]],p[i])>1) return 0;
}
return 1;
}采用gcd函数判断分组内的每一个数是否与新加进来的数互质，互质返回1，否则返回0
int gcd (int a, int b)
{
return b?gcd(b,a%b):a;
}判断这两个数的最大最大公约数，众所周知，当两个数互质时，最大公约数为1，否则肯定大于1，我们返回这两个数的最大公约数，在check函数中判断最大公约数是否大于1来判断是否互质
这一段代码为简写，此函数的正常写法和证明在下面这个链接中，大家自行阅览【模板代码】辗转相除法gcd（图像证明法）-CSDN博客
#include<bits/stdc++.h>
using namespace std;
int n;
int p[20];
int group[20][20];
bool st[20];
int res = 20;
int gcd (int a, int b)
{
return b?gcd(b,a%b):a;
}
bool check(int u,int v,int i)
{
for(int j=0;j<v;j++)
{
if(gcd(p[group[u][j]],p[i])>1) return 0;
}
return 1;
}
void dfs(int u,int v,int w,int x)
{
if(u>=res) return ;
if(w==n)
{
res=u;
return ;
}
bool flag=1;
for(int i=x;i<n;i++ )
if(!st[i] && check(u,v,i))
{
group[u][v]=i;
st[i]=1;
flag=0;
dfs(u,v+1,w+1,i+1);
st[i]=0;
}
if(flag) dfs(u+1,0,w,0);
}
int main ()
{
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
dfs(1,0,0,0);
cout<<res<<endl;
return 0;
}