La Época Dorada de Matelandia


Submit solution


Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem types
Allowed languages
C, C++, Java, Pascal, Python, VB

Un año desafortunado en Matelandia es aquel que su número n puede ser representado como n=x^a+y^b, donde a y b son dos números enteros no negativos.

Por ejemplo, si x=2 y y=3 entonces los años 4 y 17 son desafortunados (4=2^0+3^1, 17=2^3+3^2=2^4+3^0) y el año 18 no es desafortunado dado que no existe dicha representación para él.

Un intervalo de años donde no hay años desafortunados es llamado La Época Dorada.

Debes escribir un programa donde encuentres el largo máximo de La Época Dorada que comience no antes del año l y termine no luego del año r. Si todos los años en el intervalo [l, r] son desafortunados entonces la respuesta es 0.

Entrada

La primera línea contiene cuatro enteros x, y, l y r (2 \leq x, y \leq 10^{18}, 1 \leq l \leq r \leq 10^{18}).

Salida

Imprima el largo máximo de La Época Dorada dentro del rango [l, r].

Si todos los años en el intervalo [l, r] son desafortunados imprime 0.

Ejemplo #1 de Entrada

2 3 1 10

Ejemplo #1 de Salida

1

Ejemplo #2 de Entrada

3 5 10 22

Ejemplo #2 de Salida

8

Explicación

En el primer caso de prueba los años desafortunados son 2, 3, 4, 5, 7, 9, y, 10. Así que el máximo de La Época Dorada se alcanza en los intervalos [1, 1], [6, 6] y [8, 8].

En el segundo caso de prueba el máximo de La Época Dorada es el intervalo [15, 22].


Comments

There are no comments at the moment.