3689 - Fibonacci Factorial in Base B

Created by Alfredo Fundora Rolo
Added by alfredo12345 (2016-06-13)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Fibonacci numbers are mysterious and intriguing. During your practice for these programming contests, they may have already caused you a headache or two. Well, let's see if this another one of those headache-inducing problems involving Fibonacci numbers!

As you may recall, for n > 2, the n-th Fibonacci is obtained by adding (n-1)-th and (n-2)-th Fibonacci numbers. For n = 1 and n = 2, Fibonacci takes on the value of 1. So, the Fibonacci sequence starts as 1, 1, 2, 3, 5, 8, 13, ... .

Factorial of a positive integer n is defined the product of the integers from 1 to n. Let's extend the concept of Factorial to use Fibonacci numbers in the product: Fibonacci Factorial of a positive integer n is the product obtained by multiplying the first n Fibonacci numbers.

For example, the Fibonacci Factorial of 6 is obtained by multiplying:

1 * 1 * 2 * 3 * 5 * 8 = 240

Your task is simple: given a number N and a base B, determine how many trailing zeros are there in base-B representation of the Fibonacci Factorial of N. For example, if B = 2, the base-B (binary) representation of 6th Fibonacci Factorial is 11110000, which has four trailing zeros.
Los números de Fibonacci son misteriosos y fascinantes. Durante las concursos de programación, estos pueden haber sido la causa de varios dolores de cabeza. Veamos si este es otro de esos dolores de cabeza provocado por un problema relacionado con los números de Fibonacci.

Como recordarás, para n > 2, el enésimo Fibonacci se obtiene adicionando los fibonacci (n-1) y (n-2). Para   n = 1 y n = 2, el valor de Fibonacci es 1. De este modo, la secuencia de Fibonacci inicia con los valores 1, 1, 2, 3, 5, 8, 13, ... .

El factorial de un entero positivo n se define como el producto de los enteros desde 1 hasta n. Extendamos el concepto de factorial con el uso de los números de Fibonacci en el producto: el Fibonacci Factorial de un entero positivo n es el producto que se obtiene al multiplicar los primeros n números de Fibonacci.

Por ejemplo, el Fibonacci Factorial de 6 se obtiene multiplicando:

1 * 1 * 2 * 3 * 5 * 8 = 240

Su tarea es simple: dado un número N y una base B, determinar cuántos ceros hay al final de la representación en base B del Fibonacci Factorial de N. Por ejemplo, si B = 2, la representación en base B (binaria) del sexto Fibonacci Factorial es 11110000, que tiene cuatro ceros.
;jsessionid=98DE7598C0DF6BAF65882CBFE4490253
Fibonacci numbers are mysterious and intriguing. During your practice for these programming contests, they may have already caused you a headache or two. Well, let's see if this another one of those headache-inducing problems involving Fibonacci numbers!

As you may recall, for n > 2, the n-th Fibonacci is obtained by adding (n-1)-th and (n-2)-th Fibonacci numbers. For n = 1 and n = 2, Fibonacci takes on the value of 1. So, the Fibonacci sequence starts as 1, 1, 2, 3, 5, 8, 13, ... .

Factorial of a positive integer n is defined the product of the integers from 1 to n. Let's extend the concept of Factorial to use Fibonacci numbers in the product: Fibonacci Factorial of a positive integer n is the product obtained by multiplying the first n Fibonacci numbers.

For example, the Fibonacci Factorial of 6 is obtained by multiplying:

1 * 1 * 2 * 3 * 5 * 8 = 240

Your task is simple: given a number N and a base B, determine how many trailing zeros are there in base-B representation of the Fibonacci Factorial of N. For example, if B = 2, the base-B (binary) representation of 6th Fibonacci Factorial is 11110000, which has four trailing zeros.

Input specification

Input consists of multiple test cases (but no more than 2000). Each test case is in a single line and consists of two space-separated integers N (1 N 1018) and B (2 B 103). Input ends with a line with "0 0" and should not be processed.

;jsessionid=98DE7598C0DF6BAF65882CBFE4490253
La entrada consiste de varios casos de prueba (no más de 2000). Cada caso de prueba aparece en una línea y consiste de dos enteros separados por un espacio N (1 N 1018) y B (2 B 103). La entrada termina con una línea con "0 0" que no debe ser procesada.
;jsessionid=98DE7598C0DF6BAF65882CBFE4490253

Input consists of multiple test cases (but no more than 2000). Each test case is in a single line and consists of two space-separated integers N (1 N 1018) and B (2 B 103). Input ends with a line with "0 0" and should not be processed.

;jsessionid=98DE7598C0DF6BAF65882CBFE4490253

Output specification

For each test case, print a line with the required answer.
Para cada caso de prueba, imprima una línea con la respuesta requerida.

Input consists of multiple test cases (but no more than 2000). Each test case is in a single line and consists of two space-separated integers N (1 N 1018) and B (2 B 103). Input ends with a line with "0 0" and should not be processed.

;jsessionid=98DE7598C0DF6BAF65882CBFE4490253

Sample input

6 10
6 2
0 0

Sample output

1
4

Hint(s)