Module: Hàm Euler và các vấn đề khác trong lý thuyết số


Problem

9/9

**Số Fibonacci modulo (C++)

Theory Click to read/hide

Các số Fibonacci Modulo

Để tìm số Fibonacci một cách hiệu quả, chúng tôi sử dụng phép nhân ma trận, thông tin chi tiết khác tại đây.
 
Biết rằng 
\(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), viết quan hệ lặp lại cho sản phẩm ma trận:
• nếu \(m = n\) thì \(F_{2n} = F_n F_{n+1} + F_ { n-1} F_n\);
• nếu \(m = n + 1\) thì \(F_{2n+1} = F_{n+1 } F_{n+1} + F_n F_n\).
 

Problem

Như bạn đã biết, dãy Fibonacci được định nghĩa như sau:
\(F(0) = 0,\ F(1) = 1,\ F(n) = F(n – 1) + F(n – 2)\ ), cho mọi \(n > 1\).
Nó được đặt theo tên của nhà toán học người Ý Leonardo Fibonacci, còn được gọi là Leonardo của Pisa.
 
Đầu vào
Chuỗi chứa một số nguyên n (\(1 <= n <= 10^{18}\)).
 
Đầu ra
In giá trị F(n), mô-đun được tính toán \(10^8\).

Dán đoạn mã còn thiếu vào chương trình.

 

Ví dụ
<đầu>

 

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++
# Đầu vào Đầu ra
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!