7834:分成互质组
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
输入
- 第一行是一个正整数n。1 <= n <= 10。
第二行是n个不大于10000的正整数。 - 输出
- 一个正整数，即最少需要的组数。
- 样例输入
6
14 20 33 117 143 175- 样例输出
3
- 来源
- 2008年第十三届“华罗庚金杯”少年数学邀请赛 决赛第5题
- 分析：
- 这道题其实可以用DFS 加上染色的感觉。对每个数据往上判断如果不互质，那么就不能加入那个不互质的小组。还有一种可能就是自己创建一个小组.(当然可以用最优性剪枝)。
- 先发出来这段代码，还是很好理解的。
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
int n,line[15],edge[15][15],color[15],visit[15][15],ans=20,cnt;
int DFS(int x)
{
if(x>n){
if(ans>cnt)ans=cnt;
return 0;
}
memset(visit[x],1,sizeof(visit[x]));
for(int i=1;i<x;++i)
{
if(edge[i][x])continue;
visit[x][color[i]]=0;
}
for(int i=1;i<=cnt;++i)
{
if(visit[x][i]){
color[x]=i;
DFS(x+1);
}
}
if(cnt<ans){
++cnt;
color[x]=cnt;
DFS(x+1);
--cnt;
}
return 0;
}
int gcd(int a,int b)
{
return a%b==0 ? b:gcd(b,a%b);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&line[i]);
}
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
if(gcd(line[i],line[j])==1)
{
edge[i][j]=edge[j][i]=1;
}
}
}
color[1]=1;
++cnt;
DFS(2);
printf("%d",ans);
return 0;
}