Quantas Chamadas Recursivas?
Por Monirul Hasan Tomal, Southeast University 
Bangladesh
Por Monirul Hasan Tomal, Southeast University Bangladesh
Os números de fibonacci são definidos pela seguinte recorrência:
Mas não estamos interessados em números de Fibonacci aqui. Gostaríamos de saber quantas chamadas recursivas seriam necessárias para um determinado número de Fibonacci n, seguindo a recorrência normal. Uma vez que os números serão bem grandes, não será uma tarefa muito simples para você. Mas então vamos torná-la um pouco mais fácil: queremos que você apresente somente o ultimo dígito do numero de chamadas, onde este número deve estar na base b.
A entrada consiste em vários casos de teste. Para cada caso de teste haverá dois números inteiros n (0 ≤ n < (263 - 1)) e b (1 < b ≤ 10000). A entrada será terminada por um caso de teste onde n=0 e b=0, que não deve ser processada.
Para cada caso de teste deve ser impresso o número do caso de teste na saída. Em seguida, imprima n, b e o ultimo dígito (na base b) do número de chamadas. Deverá haver um único espaço entre estes dois números. Note que o ultimo dígito deverá ser apresentado no formato de um número decimal.
| Exemplo de Entrada | Exemplo de Saída |
|
0 100 |
Case 1: 0 100 1 |