Module: Rápida exponenciación


Problem

4/5

**Números de Fibonacci módulo (C++)

Theory Click to read/hide

Números del módulo de Fibonacci

Para encontrar eficientemente el número de Fibonacci, usamos la multiplicación de matrices, más detalles aquí.
 
Sabiendo que 
\(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), escribe la relación de recurrencia para producto matriz:
• si \(m = n\) entonces \(F_{2n} = F_n F_{n+1} + F_ { n-1} F_n\);
• si \(m = n + 1\) entonces \(F_{2n+1} = F_{n+1 } F_{n+1} + F_n F_n\).
 

Problem

Como sabes, la sucesión de Fibonacci se define de la siguiente manera:
\(F(0) = 0,\ F(1) = 1,\ F(n) = F(n – 1) + F(n – 2)\ ), para todos los \(n > 1\).
Lleva el nombre del matemático italiano Leonardo Fibonacci, también conocido como Leonardo de Pisa.
 
Entrada
La cadena contiene un número entero n (\(1 <= n <= 10^{18}\)).
 
Salida
Imprime el valor F(n), módulo calculado \(10^8\).

Pegue el fragmento de código que falta en el programa.

 

Ejemplos

 

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++
# Entrada Salida
1 30 832040
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!