文章目录

一.题目二.Solution三.CodeThanks!

一.题目

kate有一个集合S，S中的元素是1到n的整数。她认为集合S的一个子集M的集合的不完美值等于 ${\max }_{a,b\in M}gcd(a,b)$且$a\ne b$对于整数$k$从$2$到$n$，kate想要知道所有大小为$k$的$S$的子集中，不完美值最小是多少？ 传送门

二.Solution

这道题目太巧妙了。 首先肯定把n以内的所有质数包含1都选完，若还要继续选，我们来观察一下： 通过模拟，我们发现：

选4，此时答案是2； 其次是选6,9，此时答案是3 然后是选8，此时答案是4 选10,15,25，此时答案是5

不难发现，此时的答案就是所有数的因子中除了自己的最大因子。为什么呢？因为我们考虑如果对于数a，如果a的倍数在集合中，那么a绝对不会被删掉，我们会先考虑删除a的倍数，因此反过来，如果a在集合内，那么a的所有因子都在集合内，这样才能构造出最优解，所以答案就是集合中数的最大因子。我们用埃塞存下1~n每个数的最大因数再排个序依次输出就行了。 TQL！

三.Code

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define M 500005 int n, prime[M]; void seive (int x){ for (int i = 1; i <= n; i ++){ for (int j = i + i; j <= n; j += i){ prime[j] = i; } } } int main (){ scanf ("%d", &n); seive (n); sort (prime + 1, prime + 1 + n); for (int i = 2; i <= n; i ++) printf ("%d ", prime[i]); return 0; }

Thanks!