先考虑选出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 }
原文：https://www.cnblogs.com/PYWBKTDA/p/11870432.html
