#P4524. [Cqoi2016]伪光滑数

    ID: 3761 传统题 1000ms 512MiB 尝试: 647 已通过: 259 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索最佳优先搜索对称性去重数据结构二叉堆CF2300

[Cqoi2016]伪光滑数

[CQOI 2016] 伪光滑数

题目描述

将一个大于 11 的整数 MM 分解成质数的乘积。如果共得到 kk 个质因子,最大质因子为 pp,并且满足 pk≤Np^k\le N 和 p<128p<128,那么称 MM 为 NN-伪光滑数。

质因子按重数计算。例如 36=2×2×3×336=2\times2\times3\times3,所以 k=4k=4,p=3p=3,它是 N≥81N\ge81 时的 NN-伪光滑数。

给定 N,KN,K,将所有 NN-伪光滑数按从大到小的顺序排列,求其中第 KK 个数。

输入格式

输入一行两个整数 N,KN,K。

输出格式

输出一行一个整数,表示答案。

样例

12345 20
9167

数据范围

对于 30%30\% 的数据,N≤106N\le10^6。

对于全部数据,2≤N≤10182\le N\le10^{18},1≤K≤8000001\le K\le800000。保证至少有 KK 个符合条件的数。