Module: Euler-Funktion und andere Aufgaben der Zahlentheorie


Problem

9/9

**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

 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <map>

using namespace std;

#define MOD 100000000

map<long, long> F;

long fib(long n)
{       
}

long a;

int main()
{
	
	cin >> a;
	cout << fib(a);
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!