Berechne das n-te Fibonacci-Glied modulo m
Die Fibonacci-Folge wird dadurch definiert, dass jedes neue Glied die Summe der beiden vorherigen ist, während die ersten beiden Elemente 0 und 1 sind:
Gegeben die Zahl n, soll das n-te Fibonacci-Glied modulo m berechnet werden.
Da uns nur das Ergebnis modulo m interessiert, kann n sehr groß sein.
Eingabe
Die einzige Zeile der Eingabe enthält zwei ganze Zahlen n (0 ≤ n ≤ ) und m (1 ≤ m ≤ 50).
Ausgabe
Das Programm soll das Ergebnis von ausgeben.
Beispiele
Eingabe | Ausgabe |
|---|---|
0 5 | 0 |
1 5 | 1 |
6 5 | 3 |
Erklärung
fib(0) = 0 ⇒ 0 mod 5 = 0
fib(1) = 1 ⇒ 1 mod 5 = 1
fib(6) = 8 ⇒ 8 mod 5 = 3
Hinweis 1
Da wir die Fibonacci-Zahlen modulo m berechnen und jedes neue Glied von den beiden vorherigen abhängt, fangen die Werte irgendwann an, sich zu wiederholen. Du kannst viele Werte modulo m ausgeben und beobachten, ab wann dieses Muster erneut auftaucht.
Hinweis 2
Wenn sich die Folge nach einer Weile wiederholt, kannst du das n-te Fibonacci-Glied direkt berechnen, anstatt alle nacheinander zu durchlaufen.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB