No Adding

 

题意

有一组两两各不相同的数字,每次我们可以进行如下的操作。

取两个数字 [x,y] 如果 gcd(x,y) 没有在这组数字中将其加入这组数据。

求问,最多可以加多少组数字。

思路

如果将每个数字进行唯一分解的话,我们可以发现我们添加的数字就是那些数字的相同部分。

如果我们将这个相同部分提取出来的话,那么剩下的部分进行 gcd 的话,他们的结果一定为 1.

code

algorithm