해밍 수열

시간 제한1초메모리 제한128 MB

요약

세 소수와 순번 i가 주어질 때, 소인수가 모두 그 세 소수뿐인 1보다 큰 수 가운데 i번째로 작은 수를 구한다.

문제

세 소수 $p_1$ , $p_2$ , $p_3$ 에 대해 해밍 수열 $H(p_1, p_2, p_3)$ 을 정의한다.

$H(p_1, p_2, p_3)$ 은 소인수가 $p_1$ , $p_2$ , $p_3$ 뿐인 $1$ 보다 큰 자연수를 오름차순으로 나열한 수열이다. (즉, $1$ 은 포함하지 않는다.)

예를 들어 $H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, \dots$ 이며, 다섯 번째 수는 $6$ 이다.

첫째 줄에 $p_1$ , $p_2$ , $p_3$ , $i$ 가 주어진다. 네 정수는 모두 $10^{18}$ 보다 작다.

$H(p_1, p_2, p_3)$ 의 $i$ 번째 수를 출력한다. 출력하는 수는 $10^{18}$ 보다 작다.