web analytics

openjudge7834:分成互质组 解析报告

7834:分成互质组

总时间限制: 
1000ms

 

内存限制: 
65536kB
描述
给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

输入

第一行是一个正整数n。1 <= n <= 10。
第二行是n个不大于10000的正整数。
输出
一个正整数,即最少需要的组数。
样例输入
样例输出
来源
2008年第十三届“华罗庚金杯”少年数学邀请赛 决赛第5题
分析:
这道题其实可以用DFS 加上染色的感觉。对每个数据往上判断如果不互质,那么就不能加入那个不互质的小组。还有一种可能就是自己创建一个小组.(当然可以用最优性剪枝)。
先发出来这段代码,还是很好理解的。

Post a Comment

You must be logged in to post a comment.