Codeforces 1333 F. Kate and imperfection
在集合 S=1,2,⋯,nS={1,2,⋯,n}S=1,2,⋯,n 中，对于每个正整数 kkk ，找出一个大小为 kkk 的子集，使得该子集中两两间最大公因数的最大值最小，求这个最小值。
我们考虑如何构造两两间最大公因数的最大值最小的集合，首先肯定是把所有质数先丢进集合里，然后再把与已经在集合内的数的最大公因数 =2=2=2 的数丢进去，然后是 =3=3=3 的数……然后注意到，如果我们加入了一个合数，那么他的所有因子必定已经在集合内了，于是加入的这个数字能够产生的最大公因数就是他的最大因子，因此用埃筛维护这个贪心的过程，排序一遍输出即可。
AC代码：int n, m;
int main()
{
sd(n);
vector ans(n + 1, 1); //ans包含n+1个值为1的元素。
rep(i, 2, n)
{
for (int j = 2 * i; j <= n; j += i)
{
ans[j] = i;
}
}
sort(ans.begin(), ans.end());
rep(i, 2, n)
printf("%d%c", ans[i], i == n ? '\n' : ' ');
return 0;
}
作者：邵光亮
