Por Monirul Hasan Tomal, Southeast University Bangladesh
Los números de Fibonacci se definen por la siguiente recurrencia:
Pero no estamos interesados en los números de Fibonacci. Nos gustaría saber cuántas llamadas se necesitan para evaluar el n número de Fibonacci si seguimos la recurrencia dada. Debido a que los números van a ser bastante grandes, nos gustaría hacer el trabajo un poco fácil para usted. Sólo necesitamos el último dígito del número de llamadas, cuando este número está representado en la base b.
La entrada consta de varios casos de prueba. Para cada uno habrá dos enteros n (0 ≤ n < (263 - 1)) y b (1 < b ≤ 10000). La entrada finaliza cuando n=0 y b=0; no debe procesar este caso.
Para cada caso de prueba, imprima primero el número del caso de prueba y luego n, b y el último dígito (en base b) del número de llamadas. Debe haber un solo espacio entre los números de una línea. Notar que el último dígito tiene que ser representado en el sistema de números decimales.
Ejemplo de entrada | Ejemplo de salida |
0 100 |
Case 1: 0 100 1 |