Module: Schnelle Errichtung


Problem

4/5

**Fibonacci-Zahlen Modulo (C ++)

Theory Click to read/hide

Chisla Fibonacci auf Modul

Um Fibonaccis Nummer effektiv zu finden, verwenden wir matrische Multiplikation, ausführlicher Hier.

Wissen, dass
F_n+m} = F_m F_n+1} + F_M-1Wir erfassen das Reinheitsverhältnis für die matricianische Arbeit:
• wenn (m = n/)?;
• wenn (m = n + 1\)F_ {n+1} = F_n+1}F_n+1} + F_n F_n

Problem

Wie Sie wissen, ist die Fibonacci-Folge wie folgt definiert:
\(F(0) = 0,\ F(1) = 1,\ F(n) = F(n – 1) + F(n – 2)\), für alle \(n > 1\).
Es ist nach dem italienischen Mathematiker Leonardo Fibonacci benannt, der auch unter dem Namen Leonardo von Pisa bekannt ist.
 
Eingabe
Die Zeichenfolge enthält eine ganze Zahl n (\(1 <= n <= 10^{18}\)).
 
Ausgabe
Ausgabe des F(n)-Werts, modular berechnet \(10^8\).

Fügen Sie das fehlende Code-Snippet in das Programm ein.

 

Beispiele
Eingabe Ausgabe
1 30 832040