BOJ 2014 - 소수의 곱

 

k개의 소수들의 곱을 순서대로 나열할 때, n번째로 오는 숫자를 구하는 문제이다.

가장 단순하게 k개의 소수들로 만들 수 있는 숫자들을 만든다는 전략을 사용해 보자.

i번째로 오는 수에 k개의 소수를 각각 곱하여 만들 수 있는 수를 우선순위큐에 넣어준다.

중복되는 경우가 있을 수 있기 때문에 하나의 경우만 있을 수 있도록 처리해 준다.

 

문제의 메모리가 적으므로 메모리 초과에 유의하자.

 

#define _CRT_SECURE_NO_WARNING
#include <bits/stdc++.h>
#include <ext/rope>
#include <cassert>
#include <x86intrin.h>
using namespace std;
using namespace __gnu_cxx;

// utils
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define repair(x) x.erase(unique(all(x)),x.end())
typedef long long ll; //long long. or use int64_t
typedef long double ld; //long double
const int iinf = 1e9; //integer maximum
const long long linf = 1e18; //long long maximum
const int mod = 1e9 + 9; //prime number

// gcd, lcm, egcd funcs
template<class T>T gcd(T x, T y){if (!y)return x;return gcd(y,x%y);}
template<class T>T lcm(T x, T y){return (x*y)/gcd(x,y);}
// builtin funcs
template<class T>T bitcnt(T x){return __builtin_popcount(x);}
template<class T>T bitpar(T x){return __builtin_parity(x);}
template<class T>T bitclz(T x){return __builtin_clz(x);}
template<class T>T bitctz(T x){return __builtin_ctz(x);}
// debuging funcs
#define deb(x) cout<<#x<<": "<<(x)<<endl

//search for array
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
//////////////////////////////////////////

int k,n;
priority_queue<int,vector<int>,greater<int>>pq;
int main(){
	fastio;
	cin>>k>>n;
	vector<int>arr(k);
	for(auto&v:arr)cin>>v,pq.push(v);
	for(int i=0; i<n-1; i++){
		ll save=pq.top();
		for(int j=0; j<k; j++){
			if(save*arr[j]>=2147483647ll)continue;
			pq.push(save*arr[j]);
		}
		while(pq.top()==save)pq.pop();
	}
	cout<<pq.top();
	return 0;
}