B. The Golden Age
每次测试的时间限制
1秒
每次测试的内存限制
256字节
输入
标准输入
输出
标准输出
伯兰的不吉利年是这样的一年,它的数字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。
例子
time limit per test
1 second
memory limit per test
256 megabytes
Unlucky year in Berland is such a year that its number n can be represented as n=xa+yb, 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.
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.
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].