← 返回题目列表

Codeforces · 813/B

B. 黄金时代

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

Berland 的不吉利年份是指其编号 n 可以表示为 n = xa + yb 的年份,其中 a 和 b 为非负整数。

例如,如果 x = 2 且 y = 3,则第 4 年和第 17 年不吉利(4 = 20 + 31, 17 = 23 + 32 = 24 + 30),而第 18 年则不吉利,因为没有这样的表示。

这样的年份间隔,其中没有不吉利的年份,称为黄金时代。

你应该编写一个程序来找到黄金时代的最大长度,该长度不早于 l 年开始,不晚于 r 年结束。如果 [l, r] 区间内的所有年份都不吉利,则答案为 0。

输入

第一行包含四个整数 x、y、l 和 r (2 ≤ x, y ≤ 1018, 1 ≤ l ≤ r ≤ 1018)。

输出

打印区间 [l, r] 内《黄金时代》的最大长度。

如果区间 [l, r] 中的所有年份都不吉利,则打印 0。

示例

输入 #1

2 3 1 10

输出 #1

1

输入 #2

3 5 10 22

输出 #2

8

输入 #3

2 3 3 5

输出 #3

0

注意

在第一个示例中,不幸的年份是 2、3、4、5、7、9 和 10。因此,黄金时代的最大长度在区间 [1, 1]、[6, 6] 和 [8, 8] 中实现。

在第二个示例中,最长的黄金时代是区间 [15, 22]。