stdKonjac's Blog

An AC a day keeps the WA away ~

【Prime】

【问题描述】

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

在满足最少的组数的情况下,使得元素个数最多的那一组的元素个数尽可能的少。

【输入格式】

输入第一行是一个数n

接下来一行n个数代表a1~an

【输出格式】

输出一行两个正整数,第一个数是最少的组数,第二个数是满足最少组数的情况下,元素个数最多的那一组的元素个数。

【输入样例1】

6

14 20 33 117 143 175

【输出样例1】

3 2

【输入样例2】

4

2 4 7 9

【输出样例2】

2 2

【数据范围】

对于100%的数据:n≤15 1≤ai≤10^4.

n很小,直接DFS模拟即可。

注意记录的时候记录数的编号不要记录数值,不然求gcd慢哭会T掉1~3个点,可以先将编号之间的关系预处理出来。

考场写了个SB贪心挂掉了真是弱。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.