← 返回题目列表

AtCoder · arc042_d

D. 不多

中文机器翻译题面 查看原题

問題文

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 生成。