N-흥미로운 수

시간 제한5초메모리 제한512 MB

요약

N과 n이 주어질 때, 소인수의 개수 k와 가장 큰 소인수 p가 p^k ≤ N, p ≤ 127을 만족하는 수 중 n번째로 큰 수를 구합니다.

문제

정수 $X \ge 2$ 가 소인수분해 $X=p_1p_2\cdots p_k$ 에서 가장 큰 인수 $p_i$ 가 $p_i^k \le N$ 과 $p_i \le 127$ 을 동시에 만족할 때, 이 수를 $N$ -흥미로운 수라고 한다.

정수 $N$ 과 $n$ 이 주어진다. $N$ -흥미로운 수는 적어도 $n$ 개 존재하며, 그 개수는 유한하다고 보장된다. 큰 수부터 내림차순으로 나열했을 때 $n$ 번째 $N$ -흥미로운 수를 구하라.

첫 줄에 두 정수 $N$ 과 $n$ 이 주어진다 ( $2 \le N \le 10^{18}$ , $1 \le n \le 8 \cdot 10^5$ ).

$n$ 번째로 큰 $N$ -흥미로운 수를 정수 하나로 출력한다.