codeforce 461DIV2 F题

题意

题目给出n，k，要求找出一个1到n的子集，（a,b）的对数等于k；（a,b）满足a<b且b%a==0；

分析

还记不记得求素数的时候的欧拉筛！对就那样！如果把每个数字看作一个点的话，可以通过欧拉筛的方法求入度，然后想一想筛的时候j是如何增加的，可以n/i-1直接求出出度。知道这个结论这个题就不难了。先找到一个范围中，他的边数大于等于k，然后在这个范围内尝试删掉结点是否符合要求。（注意当i>n/2时，在n的范围内就没有出度了，所以可以确定，当在某个范围内边数大于等于k，一点可以通过删除某些结点使边数刚好达到k）。题解的最后那一部分我没有看懂（英语渣智商渣），但是通过这种方法确实可以在cf上A掉这个题；

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int maxn=+;

 int d[maxn];

 int n;

 long long k;

 int main(){

     cin>>n>>k;

     long long sum=;

     for(int i=;i<=n;i++){

         for(int j=*i;j<=n;j+=i){

             d[j]++;

             sum++;

         }

     }

     if(sum<k){

             printf("No");

             return ;

     }

     else

         printf("Yes\n");

     long long ps=;

     for(int i=;i<=n;i++){

         ps+=d[i];

         if(ps>=k){

             n=i;

             break;

         }

     }

     vector<int>ans;

     for(int i=;i<=n;i++){

         int degree=d[i]+(n/i)-;

         if(ps-degree<k){

             ans.push_back(i);

             continue;

         }

         ps-=degree;

         for(int j=*i;j<=n;j+=i){

             if(d[j])d[j]--;

         }

     }

     printf("%d\n",ans.size());

     for(int i=;i<ans.size();i++)

         printf("%d ",ans[i]);

 return ;

 }

巴特西

codeforce 461DIV2 F题

最新文章

热门文章