Background

Original problem link: P4359 [CQOI2016] Pseudo-Smooth Numbers.

Problem Description

For an integer $m > 1$, suppose its prime factorization with multiplicity has $k$ factors, and its largest prime factor is $a_k$. If it satisfies $a_{k}^{k} \leq n$ and $a_k \leq 397$, then we call $m$ an $n$-pseudo-smooth number.

Given an integer $n$, find the $k$-th largest $n$-pseudo-smooth number.

Input Format

One line with two integers $n, k$.

Output Format

One line with one integer, representing the required value.

12345 20

9167

Hint

For $100\%$ of the testdata, $1 < n \leq 10^{11}$, $k \geq 1$, and it is guaranteed that there are at least $k$ numbers that satisfy the conditions.

Translated by ChatGPT 5