[CQOI2016] 伪光滑数

题目描述

若一个大于 $1$ 的整数 $M$ 的质因数分解有 $k$ 项,其最大的质因子为 $a_k$ ,并且满足 $a_{k}^{k} \le N$,$a_k < 128$,我们就称整数 $M$ 为 $N$ - 伪光滑数。 现在给出 $N$,求所有整数中,第 $K$ 大的 $N$ - 伪光滑数。 ### 题意澄清 设 $M = 36 = 2^2 \times 3^2$,则其对应的 $k = 4$,也就是说,对 $M$ 运用唯一分解定理,$M = \prod_{i=1}^n{p_i^{c_i}}$,$k = \sum_{i=1}^n{c_i}$。 第 $K$ 大为字面意思,是真的从大到小第 $K$ 个。 modified by expect2004 2020-11-25,这或许是他退役前对洛谷公共题库的最后一次贡献

输入输出格式

输入格式


只有一行,为用空格隔开的整数 $N$ 和 $K$ 。

输出格式


只有一行,为一个整数,表示答案。

输入输出样例

输入样例 #1

12345 20

输出样例 #1

9167

说明

对于 $30\%$ 的数据,$N \le 10^6$; 对于 $100\%$ 的数据,$2 \le N \le 10^{18},1 \le K \le 800000$。保证至少有 $K$ 个满足要求的数。