Calculer le nᵉ terme de Fibonacci modulo m
La suite de Fibonacci est définie en obtenant chaque nouveau terme en additionnant les deux précédents, tandis que les deux premiers éléments sont 0 et 1 :
Étant donné un nombre n, il vous est demandé de calculer le nᵉ Fibonacci modulo m.
Comme seul le résultat modulo m nous intéresse, la valeur de n peut être très grande.
Entrée
La seule ligne de l’entrée contient deux entiers n (0 ≤ n ≤ ) et m (1 ≤ m ≤ 50).
Sortie
Le programme doit afficher le résultat de .
Exemples
Entrée | Sortie |
|---|---|
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Explication
fib(0) = 0 ⇒ 0 mod 5 = 0
fib(1) = 1 ⇒ 1 mod 5 = 1
fib(6) = 8 ⇒ 8 mod 5 = 3
Hint 1
Comme nous calculons les nombres de Fibonacci modulo m, et que chaque nouveau nombre dépend des deux précédents, ils finissent par se répéter à un certain moment. Vous pouvez essayer d’en afficher un grand nombre modulo m pour repérer le motif qui se répète.
Hint 2
Puisque les nombres finissent par se répéter à un moment donné, vous pouvez calculer directement le nᵉ nombre de Fibonacci au lieu de tout parcourir en boucle.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB