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