D：GCD

  • 集合 S 包含 1 至 n 所有的数
  • 从集合S中找任意找子集T(T中包含k个数)，都存在(存在任意两个数x,y),满足gcd(x,y) > 1
  • 求最小k

题目分析：

  • 最小k：最坏情况选择k个数满足条件
  • 素数满足两两互质、1与任何数都互质，gcd(a,b) = 1不满足gcd(x,y)>1，都要加上
  • 素数和1选择完毕，需要加上一个合数，这样就满足条件
  • 最小k：把(1~n)中所有素数筛选出来，加上1和一个合数
  • k不存在的情况是：k > n，没有k个数可以选

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 1e5 + 10;

int primes[N],cnt;
int st[N];
int n;

void get_primes(){
    mm(st,0);
    for(int i = 2; i <= n; i ++ ){
        if(!st[i]) st[i] = i,primes[++ cnt] = i;
        for(int j = 1; j <= cnt; j ++ ){
            if(primes[j] > st[i] || primes[j] > n/i) continue;
            st[i * primes[j]] = primes[j];
        } 
    }
}
int main() {
    cin >> n;
    get_primes();
    int ans = cnt + 2;
    if(ans > n) cout<<-1;
    else cout<<ans;
    return 0;
}