Kate and imperfection(数论/思维)

题目 官方题解&代码 题意：给定 n n n，表示集合 { 1 , 2 , . . . , n } \{1,2,...,n\} {1,2,...,n}，求出子集和大小为 k k k的 m a x ( g c d ( a i , a j ) ) , k = 2 , 3 , . . . , n max(gcd(a_i,a_j)),k=2,3,...,n max(gcd(ai​,aj​)),k=2,3,...,n 定义 A = a 1 , a 2 , . . . , a k A={a_1,a_2,...,a_k} A=a1​,a2​,...,ak​为一种可行的最小imperfection，如果对于 a i a_i ai​，它的一部分因子不在于集合 A A A中，那么我们可以用其中的一个因子代替 a i a_i ai​，此时集合大小不变，但他的imperfection可能变小。那么基于这个情况，我们可以假设集合 A A A任意元素的因子都在A中。定义 d ( n ) d(n) d(n)为 n n n的除了他本身的最大因子 ( d ( 1 ) = 1 ) (d(1)=1) (d(1)=1)。那么对于满足任意元素的因子都在集合中，的集合A， m a x ( a i , a j ) = m a x ( d ( a i ) ) max(a_i,a_j)=max(d(a_i)) max(ai​,aj​)=max(d(ai​))。求出 d ( ∗ ) d(*) d(∗)后，排序，即得所有的imperfection。

#include 

using namespace std;


vector max_div;

void eratosthenes(int limit) {
    max_div.assign(limit + 1, 0);
    max_div[0] = limit + 10;
    max_div[1] = 1;
    for (int i = 2; i  n;
    eratosthenes(n);
    sort(max_div.begin(), max_div.end());
    for (int i = 1; i