Calcolare l’n-esimo termine di Fibonacci modulo m
La sequenza di Fibonacci si costruisce sommando ogni volta i due termini precedenti, con i primi due elementi pari a 0 e 1:
Dato il valore di n, il compito è calcolare l’n-esimo numero di Fibonacci, prendendo il risultato modulo m.
Poiché siamo interessati unicamente al risultato modulo m, il valore di n può essere molto grande.
Input
L’unica riga di input contiene due interi n (0 ≤ n ≤ ) e m (1 ≤ m ≤ 50).
Output
Il programma deve stampare il valore di .
Esempi
Ingresso | Uscita |
|---|---|
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Spiegazione
fib(0) = 0 ⇒ 0 mod 5 = 0
fib(1) = 1 ⇒ 1 mod 5 = 1
fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
Poiché stiamo calcolando i numeri di Fibonacci modulo m, e ogni termine dipende sempre dai due precedenti, la sequenza inizierà a ripetersi dopo un certo punto. Un buon esercizio è stampare molti valori modulo m per individuare il pattern che si ripete.
Hint 2
Una volta che i numeri iniziano a ripetersi, è possibile calcolare direttamente l’n-esimo termine di Fibonacci senza dover iterare su tutti i valori.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB