CF922F Divisibility

题目链接：http://codeforces.com/contest/922/problem/F

题目大意：

　　对于一个数集 \(I\)，定义 \(f(I)\) 为 \(I\) 中满足条件的数对\((a,b)\)的个数：\(a<b\) 并且 \(a|b\).

　　要求构造一个数集 \(I\)，数集中元素大于 \(0\) 小于等于 \(n\)，并且 \(f(I) = k\).

知识点：　　构造

解题思路：

　　用一种类似素数筛的方法计算每个数的真因子的个数，顺便把个数累加起来，一旦发现大于等于\(k\)即可停止，我们用这些数来构造即可。当然，如果发现 \(1\) 到 \(n\) 所有的真因子个数加起来都小于 \(k\)，直接输出 "\(No\)".

　　接下来根据真因子个数从大到小排序，如果找到一个 \(x\) 满足：\(x > m/2\) 并且目前的 \(f( )\) 值减掉这个数真因子数大于或等于 \(k\)，就在数集中去除这个数并且更新 \(f()\) 值（因为对于大于 \(m/2\) 的数，它对于答案的贡献便是其真因子数），直到满足 \(f(I) = k\) 即可。（具体证明参考官方题解）

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef pair<ll,int> P;

 const int maxn = 3e5+;

 P have[maxn];

 bool cut[maxn];

 bool cmp(const P &a,const P &b){

     return a.first>b.first;

 }

 int main(){

     int n;

     ll k,cnt=;

     scanf("%d%lld",&n,&k);

     for(int i=;i<=n;i++)   have[i].first=,have[i].second=i;

     int m;

     for(m=;m<=n;m++){

         for(int j=m*;j<=n;j+=m) have[j].first++;

         cnt+=have[m].first;

         if(cnt>=k)  break;

     }

     if(cnt<k)   return *printf("No\n");

     sort(have+,have+m,cmp);

     int temp=m;

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

         if(have[i].second>m/&&cnt-have[i].first>=k){

             cnt-=have[i].first;

             cut[have[i].second]=true;

             temp--;

         }

         if(cnt==k)  break;

     }

     printf("Yes\n");

     printf("%d\n",temp);

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

         if(!cut[i]) printf("%d ",i);

     }

     printf("\n");

     return ;

 }

巴特西

CF922F Divisibility

最新文章

热门文章