分成互质组

题目

题目详见这里

描述

给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

输入

第一行是一个正整数n。1 <= n <= 10。
第二行是n个不大于10000的正整数。

输出

一个正整数，即最少需要的组数。

样例输入

6

14 20 33 117 143 175

样例输出

3

互质判断

在这道题中，我们需要多次判断两数是否互质，显然每次对使用枚举法判断互质会导致时间复杂度过高。

辗转相除法

辗转相除法（也称欧几里得算法）是一种常用的判断两数最大公约数的算法，具体方法为将两数中一个数数赋值为这个数与另一个数相除的余数，当一个数为零时，另一个数就是两数的最大公约数。

求 14 和 33 的最大公约数
33 / 14 = 2 余 5
14 / 5 = 2 余 4
5 / 4 =1 余 1
4 / 1 = 4 余 0
两数的最大公约数为 1 ，即两数互质

代码实现

递归

int gcd(int a,int b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}

递推

int gcd(int a,int b)
{
	a=a%b;
	while(a)
	{
		b%=a;
		swap(a,b);
	}
	return b;
}

实现

解决了判断互质后，剩下的部分就比较简单了，先对数据进行初始化，判断哪些数是互质的。
设 dfs ( now , g )，now表示现在查到了哪个数，g表示现在有几个集合，每次dfs中继续搜索将这个数放进能放的集合与自成集合，当 n 个数查完后，取 g 和 minx 的最小值即可。

#include <iostream>
using namespace std;
int a[20],cnt[20],gr[20][20],minx=2147483647,n;
int f[20][20];
int gcd(int a,int b)//辗转相除法判断互质
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
void dfs(int now,int g)//dfs找最少组数
{
	bool flag=1;
	if(now>n)
	{
		minx=min(minx,g);
		return ;
	}
	for(int i=1;i<=g;i++)
	{
		flag=1;
		for(int j=1;j<=cnt[i];j++)
		{
			if(f[now][gr[i][j]]==0)
			{
				flag=0;
				break;
			}
		}
		if(flag)
		{
			gr[i][++cnt[i]]=now;
			dfs(now+1,g);
			--cnt[i];
		}
	}
	gr[g+1][++cnt[g+1]]=now;
	dfs(now+1,g+1);
	return ;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		for(int j=1;j<i;j++)
		{
			if(gcd(a[i],a[j])==1)//数据预处理
			{
				f[i][j]=f[j][i]=1;
			}
		}
	}
	dfs(1,0);
	cout<<minx;
	return 0;
}