問題文
4 整数 X, P, A, B (1 ≦ X < P < 2^{31}, 0 ≦ A ≦ B < 2^{31}) 。然而,P 是质数。 求除以 X^i (A ≦ i ≦ B) 在 P 后余数的最小值。
该题的输入示例不影响分数 除了 1 除了这个 C++ 程序 使用生成。用于初始化伪随机数生成器的程序的第一部分是 1 论点是 1 以上 10,000 使用以下整数。这个文件的 i 行目 (1 ≦ i ≦ 10,000) 是输入生成器的第一个 1 论点是 匹配 i 时的输出。即给出的测试用例是一个输入示例 匹配此文件中除 1 之外的任何行。 在
入力
输入是按以下格式从标准输入给出的。
X P A B
- 1 行中,4 整数 X, P, A, B (1 ≦ X < P < 2^{31}, 0 ≦ A ≦ B < 2^{31}) 用空格分隔。然而,P 是质数。 除以
出力
X^i (A ≦ i ≦ B) 在 P 后余数的最小值为 除以 1 行输出。
入力例1
2 11 3 9
出力例1
3
X^i (A ≦ i ≦ B) 在 P 的余数为 8, 5, 10, 9, 7, 3, 6 ,所以最小值是 3 。 此输入不是使用输入生成器创建的,因此它不会影响您收到的分数。
入力例2
15 7159 12 12818
出力例2
1
该输入是输入生成器的第一个输入。 1 在参数中 通过给予 1 生成。
入力例3
1400884 50141599 4 458568
出力例3
114
该输入是输入生成器的第一个输入。 1 在参数中 通过给予 3 生成。
入力例4
1591755 291456379 215 1223
出力例4
96324
该输入是输入生成器的第一个输入。 1 在参数中 通过给予 25 生成。