南沙C++信奥老师解一本通题 1221：分成互质组
【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
【输入】
第一行是一个正整数n。1 ≤ n ≤ 10。
第二行是n个不大于10000的正整数。
【输出】
一个正整数，即最少需要的组数。
【输入样例】
6
14 20 33 117 143 175
【输出样例】
3
#include <bits/stdc++.h>
using namespace std;
int a[11],path[11][11],ans=0x3f3f3f3f,n; //path[i][j] 行 表示有i组，每组有多少个元素
int gcd(int a,int b) //辗转相除法
{
return a%b==0?b:gcd(b,a%b);
}
void dfs(int pos,int cnt)//pos为要放当前的位置,cnt存的当前查找到的分组个数
{
if(pos==n+1)
{
ans=min(ans,cnt);
return;
}//尝试 将某个数放到某其中一组能互质的，不是只要能互质就固定下来，要尝次多组互质都要试下，也要尝试自己单独一组
for(int i=1;i<=cnt;i++) //共有cnt组 一情况情组可以放得下
{
bool flag=true;
for(int j=1;j<pos;j++)
{
if( path[i][j]!=0 && gcd( a[pos], path[i][j] ) !=1 ) //互质
{
flag=false;
break;// 不能放到这组
}
}
if(flag)
{
path[i][pos]=a[pos];
dfs(pos+1,cnt);
}
}
//自己单独作为一组
path[cnt+1][pos]=a[pos];
dfs(pos+1,cnt+1);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(1,1);//从数组1开始
cout<<ans;
return 0;
}
原文地址：https://blog.csdn.net/vx_cyf1333888/article/details/142632702
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！