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