【gcd】【桶】【僞暴力】欠扁的CD

題目

解

用一個桶存下a[i]。

暴力枚舉gcd，從max(a[i])直接往下枚舉，然後枚舉這個gcd的倍數，統計它的倍數有多少，達到k了就可直接輸出。

代碼

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll n,k,lj,maxx,a[500001],t[500001];
int main(){
 scanf("%lld%lld",&n,&k);
 for(ll i = 1; i <= n; ++i){
  scanf("%lld", &a[i]);
  maxx = max(maxx, a[i]);  //取max
  ++t[a[i]];  //桶
 }
 for(ll i = maxx; i; --i){  //枚舉gcd
  lj = 0;
  for(ll j = i; j <= maxx; j += i){  //gcd的倍數
   lj += t[j];  //累計倍數個數
   if(lj >= k){  //達到目标
    printf("%lld",i*k);
    return 0;
   }
  }
 }
}