English · Original
Chinese · Translation
Formal · Original
_Unlucky_ year in Berland is such a year that its number _n_ can be represented as _n_ = _x__a_ + _y__b_, where _a_ and _b_ are non-negative integer numbers.
For example, if _x_ = 2 and _y_ = 3 then the years _4_ and _17_ are _unlucky_ (4 = 20 + 31, 17 = 23 + 32 = 24 + 30) and year _18_ isn't _unlucky_ as there is no such representation for it.
Such interval of years that there are no _unlucky_ years in it is called _The Golden Age_.
You should write a program which will find maximum length of _The Golden Age_ which starts no earlier than the year _l_ and ends no later than the year _r_. If all years in the interval \[_l_, _r_\] are _unlucky_ then the answer is _0_.
## Input
The first line contains four integer numbers _x_, _y_, _l_ and _r_ (2 ≤ _x_, _y_ ≤ 1018, 1 ≤ _l_ ≤ _r_ ≤ 1018).
## Output
Print the maximum length of _The Golden Age_ within the interval \[_l_, _r_\].
If all years in the interval \[_l_, _r_\] are _unlucky_ then print _0_.
[samples]
## Note
In the first example the _unlucky_ years are _2, 3, 4, 5, 7, 9_ and _10_. So maximum length of _The Golden Age_ is achived in the intervals \[1, 1\], \[6, 6\] and \[8, 8\].
In the second example the longest _Golden Age_ is the interval \[15, 22\].
在Berland，_不幸_年份是指其年份数 #cf_span[n] 可以表示为 #cf_span[n = xa + yb] 的年份，其中 #cf_span[a] 和 #cf_span[b] 是非负整数。
例如，若 #cf_span[x = 2] 且 #cf_span[y = 3]，则年份 _4_ 和 _17_ 是 _不幸_ 的（#cf_span[4 = 20 + 31]，#cf_span[17 = 23 + 32 = 24 + 30]），而年份 _18_ 不是 _不幸_ 的，因为不存在这样的表示。
若一个年份区间内不存在任何 _不幸_ 年份，则称该区间为 _黄金时代_。
你需要编写一个程序，找出在区间 #cf_span[[l, r]] 内、起始时间不早于 #cf_span[l] 且结束时间不晚于 #cf_span[r] 的 _黄金时代_ 的最大长度。如果区间 #cf_span[[l, r]] 中的所有年份都是 _不幸_ 的，则答案为 _0_。
第一行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[l] 和 #cf_span[r]（#cf_span[2 ≤ x, y ≤ 1018]，#cf_span[1 ≤ l ≤ r ≤ 1018]）。
请输出在区间 #cf_span[[l, r]] 内 _黄金时代_ 的最大长度。
如果区间 #cf_span[[l, r]] 中的所有年份都是 _不幸_ 的，则输出 _0_。
在第一个例子中，_不幸_ 年份为 _2, 3, 4, 5, 7, 9_ 和 _10_。因此，_黄金时代_ 的最大长度在区间 #cf_span[[1, 1]]、#cf_span[[6, 6]] 和 #cf_span[[8, 8]] 中取得。
在第二个例子中，最长的 _黄金时代_ 是区间 #cf_span[[15, 22]]。
## Input
第一行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[l] 和 #cf_span[r]（#cf_span[2 ≤ x, y ≤ 1018]，#cf_span[1 ≤ l ≤ r ≤ 1018]）。
## Output
请输出在区间 #cf_span[[l, r]] 内 _黄金时代_ 的最大长度。如果区间 #cf_span[[l, r]] 中的所有年份都是 _不幸_ 的，则输出 _0_。
[samples]
## Note
在第一个例子中，_不幸_ 年份为 _2, 3, 4, 5, 7, 9_ 和 _10_。因此，_黄金时代_ 的最大长度在区间 #cf_span[[1, 1]]、#cf_span[[6, 6]] 和 #cf_span[[8, 8]] 中取得。在第二个例子中，最长的 _黄金时代_ 是区间 #cf_span[[15, 22]]。
**Definitions**
Let $ x, y \in \mathbb{Z}_{\geq 2} $, $ l, r \in \mathbb{Z} $ with $ 1 \leq l \leq r \leq 10^{18} $.
Let $ U = \{ n \in \mathbb{Z} \mid n = xa + yb,\ a, b \in \mathbb{Z}_{\geq 0} \} $ be the set of *unlucky* years.
Let $ G = [l, r] \setminus U $ be the set of *lucky* (non-unlucky) years in the interval $[l, r]$.
**Constraints**
$ 2 \leq x, y \leq 10^{18} $,
$ 1 \leq l \leq r \leq 10^{18} $
**Objective**
Find the maximum length of a contiguous interval $ [a, b] \subseteq [l, r] $ such that $ [a, b] \cap U = \emptyset $.
That is, compute:
$$
\max \left\{ b - a + 1 \mid [a, b] \subseteq [l, r],\ [a, b] \cap U = \emptyset \right\}
$$
If no such interval exists (i.e., $ G = \emptyset $), output $ 0 $.
API Response (JSON)
{
"problem": {
"name": "B. The Golden Age",
"description": {
"content": "_Unlucky_ year in Berland is such a year that its number _n_ can be represented as _n_ = _x__a_ + _y__b_, where _a_ and _b_ are non-negative integer numbers. For example, if _x_ = 2 and _y_ = 3 then ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF813B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_Unlucky_ year in Berland is such a year that its number _n_ can be represented as _n_ = _x__a_ + _y__b_, where _a_ and _b_ are non-negative integer numbers.\n\nFor example, if _x_ = 2 and _y_ = 3 then ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在Berland，_不幸_年份是指其年份数 #cf_span[n] 可以表示为 #cf_span[n = xa + yb] 的年份，其中 #cf_span[a] 和 #cf_span[b] 是非负整数。\n\n例如，若 #cf_span[x = 2] 且 #cf_span[y = 3]，则年份 _4_ 和 _17_ 是 _不幸_ 的（#cf_span[4 = 20 + 31]，#cf_span[17 ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ x, y \\in \\mathbb{Z}_{\\geq 2} $, $ l, r \\in \\mathbb{Z} $ with $ 1 \\leq l \\leq r \\leq 10^{18} $. \nLet $ U = \\{ n \\in \\mathbb{Z} \\mid n = xa + yb,\\ a, b \\in \\mathbb{Z}_{\\geq 0} \\...",
"is_translate": false,
"language": "Formal"
}
]
}