{"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 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.\n\nSuch interval of years that there are no _unlucky_ years in it is called _The Golden Age_.\n\nYou 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_.\n\n## Input\n\nThe first line contains four integer numbers _x_, _y_, _l_ and _r_ (2 ≤ _x_, _y_ ≤ 1018, 1 ≤ _l_ ≤ _r_ ≤ 1018).\n\n## Output\n\nPrint the maximum length of _The Golden Age_ within the interval \\[_l_, _r_\\].\n\nIf all years in the interval \\[_l_, _r_\\] are _unlucky_ then print _0_.\n\n[samples]\n\n## Note\n\nIn 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\\].\n\nIn the second example the longest _Golden Age_ is the interval \\[15, 22\\].","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 = 23 + 32 = 24 + 30]），而年份 _18_ 不是 _不幸_ 的，因为不存在这样的表示。\n\n若一个年份区间内不存在任何 _不幸_ 年份，则称该区间为 _黄金时代_。\n\n你需要编写一个程序，找出在区间 #cf_span[[l, r]] 内、起始时间不早于 #cf_span[l] 且结束时间不晚于 #cf_span[r] 的 _黄金时代_ 的最大长度。如果区间 #cf_span[[l, r]] 中的所有年份都是 _不幸_ 的，则答案为 _0_。\n\n第一行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[l] 和 #cf_span[r]（#cf_span[2 ≤ x, y ≤ 1018]，#cf_span[1 ≤ l ≤ r ≤ 1018]）。\n\n请输出在区间 #cf_span[[l, r]] 内 _黄金时代_ 的最大长度。\n\n如果区间 #cf_span[[l, r]] 中的所有年份都是 _不幸_ 的，则输出 _0_。\n\n在第一个例子中，_不幸_ 年份为 _2, 3, 4, 5, 7, 9_ 和 _10_。因此，_黄金时代_ 的最大长度在区间 #cf_span[[1, 1]]、#cf_span[[6, 6]] 和 #cf_span[[8, 8]] 中取得。\n\n在第二个例子中，最长的 _黄金时代_ 是区间 #cf_span[[15, 22]]。\n\n## Input\n\n第一行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[l] 和 #cf_span[r]（#cf_span[2 ≤ x, y ≤ 1018]，#cf_span[1 ≤ l ≤ r ≤ 1018]）。\n\n## Output\n\n请输出在区间 #cf_span[[l, r]] 内 _黄金时代_ 的最大长度。如果区间 #cf_span[[l, r]] 中的所有年份都是 _不幸_ 的，则输出 _0_。\n\n[samples]\n\n## Note\n\n在第一个例子中，_不幸_ 年份为 _2, 3, 4, 5, 7, 9_ 和 _10_。因此，_黄金时代_ 的最大长度在区间 #cf_span[[1, 1]]、#cf_span[[6, 6]] 和 #cf_span[[8, 8]] 中取得。在第二个例子中，最长的 _黄金时代_ 是区间 #cf_span[[15, 22]]。","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} \\} $ be the set of *unlucky* years.  \nLet $ G = [l, r] \\setminus U $ be the set of *lucky* (non-unlucky) years in the interval $[l, r]$.\n\n**Constraints**  \n$ 2 \\leq x, y \\leq 10^{18} $,  \n$ 1 \\leq l \\leq r \\leq 10^{18} $\n\n**Objective**  \nFind the maximum length of a contiguous interval $ [a, b] \\subseteq [l, r] $ such that $ [a, b] \\cap U = \\emptyset $.  \nThat is, compute:  \n$$\n\\max \\left\\{ b - a + 1 \\mid [a, b] \\subseteq [l, r],\\ [a, b] \\cap U = \\emptyset \\right\\}\n$$  \nIf no such interval exists (i.e., $ G = \\emptyset $), output $ 0 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF813B","tags":["brute force","math"],"sample_group":[["2 3 1 10","1"],["3 5 10 22","8"],["2 3 3 5","0"]],"created_at":"2026-03-03 11:00:39"}}