HDOJ 5902 GCD is Funny

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5902

题目翻译

Alex发明了一个有趣的游戏. 一开始他在黑板上写了nn个正整数, 然后他开始重复进行如下的操作:

  1. 他选择黑板上三个数字a, b和c, 把他们从黑板上擦掉.
  2. 他从这三个数a, b和c中选择了两个数, 并计算出他们的最大公约数, 记这个数为d (d 可以是\(\gcd(a,b)\), \(\gcd(a,c)\)或者\(\gcd(b, c)\)).
  3. 他在黑板上写下两次数字d.

显然, 在操作(n-2)次后, 黑板上只会留下两个相同的数字. Alex想要知道哪些数字可以最终可能留在黑板上.

题解

在第一次选择3个数字(a,b,c)的时候,我们一定会扔掉一个数字,然后放入两个相同的数字GCD(a,b)。接下来的每次数字选择,我们都可以选择扔掉之前产生的有重复的数字,也可以扔掉之前从未使用过的数字。
所以,这样一看,最后可能留在黑板上的数字一定是原来留在黑板上的N个数字中,其中 2 ~ n-1 个数字的GCD。所以我们只需要循环把他们算出来即可。

代码