分为互质组
题目描述：
蒜头君给定 n 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
输入：
第一行是一个正整数 n。1≤n≤10。 第二行是 n 个不大于10000 的正整数。
输出：
一个正整数，即最少需要的组数。 输出时每行末尾的多余空格，不影响答案正确性
解题思路：
1.本题采用dfs来搜索，首先用一个函数来判断两个数是否互质 2.从第一个数开始，先分一组，然后用一个数组保存第这个数在哪个组中，然后继续搜索，如果这个数和这个组中所有数都互质，则加入这个组，若都不互质，直接再开一个新的组，继续搜索。
代码：
#include <iostream> #define inf 0x3f3f3f3f int n,flag,a[15],b[15],sum=inf; using namespace std; int f(int a,int b)//返回1则互质 { if(b==0) return a; else return f(b,a%b); } void dfs(int x,int num)//第x个数，num组 { if(x==n+1) { sum=min(sum,num); return; } for(int i=1;i<=num;i++) { flag=1; for(int j=1;j<x;j++) { if(b[j]==i)//第j个数在第i组中 { if(f(a[x],a[j])!=1)//不互质 { flag=0; break; } } } if(flag) { b[x]=i; dfs(x+1,num); b[x]=0; } } if(!flag) { b[x]=num+1; dfs(x+1,num+1); b[x]=0; } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } dfs(1,1); cout<<sum<<endl; return 0; }