Calcular o n-ésimo termo de Fibonacci módulo m
A sequência de Fibonacci é definida ao obter cada próximo termo somando os dois termos anteriores, sendo que os dois primeiros elementos são 0 e 1:
Dado o número
n, é pedido que calcule o n-ésimo número de Fibonacci módulo m.Como apenas nos interessa o resultado em módulo
m, o valor de n pode ser muito grande.Entrada
A única linha de entrada contém dois inteiros
n (0 ≤ n ≤ ) e m (1 ≤ m ≤ 50).Saída
O programa deve imprimir o resultado de .
Exemplos
Input | Output |
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Explicação
- fib(0) = 0 ⇒ 0 mod 5 = 0
- fib(1) = 1 ⇒ 1 mod 5 = 1
- fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
Como estamos a calcular os números de Fibonacci módulo
m, e o próximo número depende sempre dos dois anteriores, a certa altura os valores começam a repetir-se. Pode tentar imprimir muitos valores em módulo m e observar o padrão a partir do qual eles voltam a repetir.Hint 2
Assim que os números começam a repetir-se após um certo ponto, é possível calcular diretamente o número de Fibonacci na posição
n em vez de percorrer todos eles.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB