整数的素因子数

整数的素因子数

测试数据来自 system/2036

描述

Q先生是一个热爱学习的男孩子。

他知道任意正整数存在唯一的素数分解,在不忽略重数的情况下统计分解后得到的素数个数,就是这个整数的素因子个数。
例如 120=23×3×5120=2^3 \times 3\times 5,所以 12012055 个素因子。

现在他给定了正整数 nn 与另外一个正整数 pp,希望你找到第 nn 个(也就是第 nn 小的)有至少 nn 个素因子的整数,并输出其模 pp 后的余数。

格式

输入格式

输入有一行,包含两个由空格隔开的正整数,分别为 nnpp

输出格式

输出一个正整数,表示第 nn 个有至少 nn 个素因子的整数模 pp 后的余数。

样例1

样例输入1

5 123454321

样例输出1

80

样例说明1

66 个有不少于 55 个素因子的正整数依次为:32=2532=2^5, 48=24348=2^43, 64=2664=2^6, 72=233272=2^33^2, 80=24580=2^4596=25396=2^53

样例2

样例输入2

100 123454321

样例输出2

49932491

限制

对于 30%30\% 的数据,有 5n5005\le n\le 500

对于 60%60\% 的数据,有 5n50005\le n\le 5000

对于 100%100\% 的数据,有 5n500005\le n\le 50000108p2×10810^8 \le p \le 2\times 10^8

每一组数据时限为1秒。

信息

ID
1085
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者