题意: #
定义如下序列的变换(由一个已知序列生成另一个序列):
如果序列是空的则停止,否则在新序列的最后加上当前序列所有元素的 gcd,然后从原序列中移除一个元素。重复上述操作直到停止,问能得到的最大字典序的序列。
题很简单,相信聪明的你一定能做出来。
思路 #
很显然,前面几个数必然是 1,所以要想让字典序尽量大就得尽快出现别的数,要想让一个数出现就得删掉全部不是它倍数的数,那么最快能出现的数就是 2 了,只要把所有奇数删掉就行了。然后就剩下了一堆偶数,是不是看起来似曾相识?没错他又变成了刚才的问题只不过所有数都乘了 2(禁止套娃)。那啥时候停呢?当 n 小于 3 的时候,因为此时无法用刚才的规律。
是不是很有意思呢?其实递归的题都挺有意思的。
代码 #