[bzoj2257]瓶子和燃料

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

先考虑选出k个后答案最小会是多少，容易发现其实就是所有的gcd（就是$ax+by=gcd(a,b)$的推广）
然后相当于要最大化gcd，反过来可以将所有数的约数都打上+1标记，+1标记不少于k个且最大的数就是答案，由于值域较大，需要用map来维护

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,k,x,ans;

 4 map<int,int>s;

 5 map<int,int>::iterator it;

 6 int main(){

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

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

 9         scanf("%d",&x);

10         for(int j=1;j*j<=x;j++)

11             if (x%j==0){

12                 s[x/j]++;

13                 if (j*j!=x)s[j]++;

14             }

15     }

16     for(it=s.begin();it!=s.end();it++)

17         if ((*it).second>=k)ans=(*it).first;

18     printf("%d",ans);

19 }