@ysner
2018-06-08T14:19:28.000000Z
字数 870
阅读 1959
数论
现有个数,询问选出个数的的最大值。
枚举。
枚举最大值,看是否有个数能将其除尽。
话说我想了半天为什么不给出的范围,竟然没想到是因要开桶,的范围无意义。。。
于是我们开个桶记录每个数出现多少次。
然后枚举最大值。
要判断有多少个数能将其除尽,直接枚举算即可。
复杂度最坏为
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,k,a[N],ans=1,mx;
int main()
{
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
n=gi();k=gi();
fp(i,1,n)
{
re int x=gi();mx=max(mx,x);
a[x]++;
}
fq(i,mx,1)
{
re int sum=0;
for(re int j=1;j*i<=mx;j++) sum+=a[j*i];
if(sum>=k) {printf("%lld\n",1ll*k*i);return 0;}
}
fclose(stdin);
fclose(stdout);
return 0;
}