#1533. 最大净商问题

最大净商问题

题目描述

NN 个连续自然数 x,x+1,x+2x,x+1,x+2 一直到 x+N1x+N-1。已知 NN,求那 NN 个数的乘积除以那 NN 个数的最小公倍数的商 QQ 的最大值。

数学课上,首先发现这个问题的公式的人把它叫做「最大净商问题」,其中的 QQ 就是「净商」。


求:

$$\max\left\{\frac{\prod_{i=x}^{x+N-1} i}{\mathrm{lcm}(x,x+1,\ldots ,x+N-1)}\right\} $$

输入格式

一行,包含两个数 NNPP

输出格式

最大净商 QQPP 的值。

样例 1

3 1000000007
2

如果 x=4x = 4,那么 Q=12060=2Q = \frac{120}{60} = 2。没有更好的方法了,所以输出 22

19 1000000007
557316307

记得将答案模 PP

数据范围与提示

对于 100%100\% 的数据,1N1061 \le N \le 10^6PP 为质数。