题意: 在集合 S=1,2,⋯,nS={1,2,⋯,n}S=1,2,⋯,n 中,对于每个正整数 kkk ,找出一个大小为 kkk 的子集,使得该子集中两两间最大公因数的最大值最小,求这个最小值。 我们考虑如何构造两两间最大公因数的最大值最小的集合,首先肯定是把所有质数先丢进集合里,然后再把与已经在集合内的数的最大公因数 =2=2=2 的数丢进去,然后是 =3=3=3 的数......然后注意到,如果我们加入了一个合数,那么他的所有因子必定已经在集合内了,于是加入的这个数字能够产生的最大公因数就是他的最大因子,因此用埃筛维护这个贪心的过程,排序一遍输出即可。 AC代码: int n, m; int m