Tenemos un número $k$ y tenemos que encontrar el menor número de Fibonacci que tenga factor común con él(excepto $1$ ). También tenemos $2 \leq k \leq 1,000,000$ .
Se garantiza que el número de Fibonacci requerido es menor que $10^{18}$ .
Respuesta
¿Demasiados anuncios?
user8269
Puntos
46
Encuentra todos los primos que dividen $k$ . Ejecuta la recursión de Fibonacci modulo cada uno de estos primos. Mira cuál te da primero el cero. Por ejemplo, si $k=667=23\times29$ la secuencia reducida a módulo 23 es $$1,1,2,3,5,8,13,21,11,9,20,6,3,9,12,21,10,8,18,3,21,1,22,0$$ por lo que el 24º número de Fibonacci es un múltiplo de 23; módulo 29, se obtiene $$1,1,2,3,5,8,13,21,5,26,2,28,1,0$$ por lo que el 14º Fibonacci es un múltiplo de 29. $14\lt24$ por lo que el 14º Fibonacci (que es $377=13\times29$ ) es el primero con un factor común no trivial con $k$ .
