https://www.luogu.com.cn/problem/CF582A
这道题的核心做法是从大到小来算;
因为gcd(a,b)<=min(a,b),所以最大的数一定是序列中的数,现在看第二大的数:也必须是序列中的,第三大的:如果我们把两个 gcd(x,k) 都从数表中剔除,那么可以认为 x,k 就不会对数表中的最大值产生影响了(因为开头的结论),那么此时数表中的最大值就又一定出现在原数列中了。
再接下来的最大值呢?可能是上面三个的 gcd,但只要把它们都剔除(两个),就又不会有影响了。
由此,我们得到了此题的解法:每次把数表中的最大值取出来,它是原数列中的数。然后,把它与之前被取出来的 gcd 都从数表中剔除。如此循环往复,直到取满 n 个数或数表被取空为止。