소수의 곱
면접 대비시간 제한2초메모리 제한128 MB
주어진 K개의 소수를 하나 이상 곱해 만들 수 있는 수들을 증가하는 순서로 나열했을 때 N번째 값을 힙으로 구합니다.
문제
서로 다른 소수 K개가 주어진다. 이 소수들 중 하나 이상을 골라 곱해서 만들 수 있는 모든 양의 정수를 생각하자. 같은 소수를 여러 번 골라도 되고, 소수 하나만 고르는 경우도 포함한다.
소수가 2, 5, 7이면 만들 수 있는 수를 오름차순으로 나열했을 때 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, ...로 시작한다.
주어진 K개의 소수로 만들 수 있는 수들을 오름차순으로 나열했을 때 N번째 수를 구하자. 정답은 2^31보다 작은 양의 정수이다.
입력
첫째 줄에 K와 N이 주어진다 (1 <= K <= 100, 1 <= N <= 100000).
둘째 줄에는 서로 다른 소수 K개가 오름차순으로 주어진다. 각 소수는 541 이하의 양의 정수이다.
출력
위에서 설명한 수열에서 N번째 수를 출력한다.