【题目描述】
给定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;
}
