1276: #2047. 「CQOI2016」伪光滑数

Memory Limit:512 MB Time Limit:3.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

若一个大于 111 的整数 MMM 的质因数分解有 kkk 项,其最大的质因子为 aka_kak,并且满足 akk≤N{a_k}^k \leq NakkNak<128a_k < 128ak<128,我们就称整数 MMMNNN-伪光滑数。

现在给出 NNN,求所有整数中,第 KKK 大的 NNN-伪光滑数。

输入格式

只有一行,为用空格隔开的整数 NNNKKK

输出格式

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

样例

样例输入

12345 20

样例输出

9167

数据范围与提示

对于 30%30\%30% 的数据,N≤106N \leq 10^6N106
对于 100%100\%100% 的数据,2≤N≤10182 \leq N \leq 10^{18}2N10181≤K≤8000001 \leq K \leq 8000001K800000。保证至少有 KKK 个满足要求的数。