2014 - 소수의 곱

 

2014번: 소수의 곱

#include <stdio.h>

typedef long long ll;

const ll LK = 1e2;
const ll LN = 1e5;

ll K, N, R;
ll arr[LK + 10];

void swap(ll& x, ll& y) {ll z = x; x = y; y = z;}
int minComp(ll x, ll y) {return x < y;}

struct PQ {
  ll hn;
  ll heap[LN * 10 + 10];
  int (*comp)(ll, ll);


  void init() {
    hn = 0;
    comp = minComp;
  }

  void push(ll x) {
    heap[++hn] = x;

    for (int c = hn; c > 1; c /= 2) {
      if (comp(heap[c], heap[c / 2])) { swap(heap[c], heap[c / 2]); }
      else break;
    }
  }

  ll pop() {
    swap(heap[1], heap[hn--]);

    for (int c = 2; c <= hn; c *= 2) {
      if (c < hn && comp(heap[c + 1], heap[c])) {c++;}
      if (comp(heap[c], heap[c / 2])) { swap(heap[c], heap[c / 2]); }
      else break;
    }

    return heap[hn + 1];
  }
} minq;

void init() {
  minq.init();

  scanf("%lld %lld", &K, &N);

  for (int k = 0; k < K; ++k) {
    scanf("%lld", &arr[k]);

    minq.push(arr[k]);
  }
}

void cal() {
  ll val;
  int cnt = 0;

  while (minq.hn) {
    val = minq.pop();

    if (++cnt == N) {
      R = val;

      return;
    }

    for (int k = 0; k < K; ++k) {
      minq.push(arr[k] * val);

      if (val % arr[k] == 0) {
        break;
      }
    }
  }
}

int main(void) {
  // freopen("2014.txt", "r", stdin);

  init();

  cal();

  printf("%lld", R);

  return 0;
}

 

범위 조심