Notar que ~x^a~ para ~x \geq 2~ no tiene mas de 60 potencias que den valores no mayores de ~10^{18}~.

Por tanto vamos a almacenar todas las posibles sumas de todas las potencias de ~x~ y ~y~. Ahora la respuesta puede ser obtenida en tiempo lineal al revisar cual es la diferencia entre los años desafortunados vecinos en la lista ordenada.

No olvidar que debes manejar cuidadosamente la multiplicación de números tan grandes para evitar obtener RTE al exceder números de 64-bits. Por ejemplo, en vez de escribir

while (num <= 1e18)
   num = num * x

o

while (num * x <= 1e18)
   num = num * x

deberías escribir

while (num <= 1e18 / x)
    num = num * x

Complejidad total: ~O(nlogn)~

Link del problema en Codeforces