TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3616
  • 题目
  • P3616【CQOI2016 Day2】伪光滑数
    限制 : 时间限制 : 30000 MS   空间限制 : 524288 KB
    问题描述

            若一个大于1的整数M的质因数分解有k项,其最大的质因子为ak,并且满足akk≤N,ak<128,我们就称整数M为N-伪光滑数。
            现在给出N,求所有整数中,第K大的N-伪光滑数。

    输入格式

            输入文件内容只有一行,为用空格隔开的整数N和K。

    输出格式

            输出文件内容只有一行,为一个整数,表示答案。

    样例输入

    12345 20

    样例输出

    9167

    提示

    样例解释:
            前20大的12345-伪光滑数列列举如下:
                    1.12167=232323;
                    2.11881=109109;
                    3.11663=107
    109;
                    4.11449=107107;
                    5.11227=103
    109;
                    6.11021=103107;
                    7.11009=101
    109;
                    8.10807=101107;
                    9.10609=103
    103;
                    10.10573=97109;
                    11.10403=101
    103;
                    12.10379=97107;
                    13.10201=101
    101;
                    14.10051=192323;
                    15.9991=97103;
                    16.9797=97
    101;
                    17.9701=89109;
                    18.9523=89
    107;
                    19.9409=9797;
                    20.9167=89
    103;

    数据范围:
            对于30%的数据,N≤106
            对于60%的数据,K≤105
            对于100%的数据,2≤N≤1018,1≤K≤8*105,保证至少有K个满足要求的数。


    来源  感谢nodgd闲的蛋疼去验算样例解释