整数的素因子数
测试数据来自 system/2036
描述
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
- 1085
- 难度
- (无)
- 分类
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者