/ Vijos / 题库 /

整数的素因子数

整数的素因子数

描述

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

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

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

格式

输入格式

输入有一行,包含两个由空格隔开的正整数,分别为 \(n\) 和 \(p\)。

输出格式

输出一个正整数,表示第 \(n\) 个有至少 \(n\) 个素因子的整数模 \(p\) 后的余数。

样例1

样例输入1

5 123454321

样例输出1

80

样例说明1

前 \(6\) 个有不少于 \(5\) 个素因子的正整数依次为:\(32=2^5\), \(48=2^43\), \(64=2^6\), \(72=2^33^2\), \(80=2^45\) 和 \(96=2^53\)。

样例2

样例输入2

100 123454321

样例输出2

49932491

限制

对于 \(30\%\) 的数据,有 \(5\le n\le 500\)。

对于 \(60\%\) 的数据,有 \(5\le n\le 5000\)。

对于 \(100\%\) 的数据,有 \(5\le n\le 50000\) 且 \(10^8 \le p \le 2\times 10^8\)。

每一组数据时限为1秒。

信息

ID
2036
难度
9
分类
(无)
标签
(无)
递交数
14
已通过
1
通过率
7%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

又是一年省选季之春分邀请赛