#2047. 「CQOI2016」伪光滑数

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

若一个大于 1 的整数 M 的质因数分解有 k 项,其最大的质因子为 a_k ,并且满足 {a_k}^k \leq N a_k < 128 ,我们就称整数 M N -伪光滑数。

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

输入格式

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

输出格式

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

样例

样例输入

12345 20

样例输出

9167

数据范围与提示

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