**Числа Фибоначчи по модулю (С++) - Быстрое возведение в степень

Для эффективного нахождения числа Фибоначчи воспользуемся матричным умножением, подробзее здесь: http://e-maxx.ru/algo/binary_pow

зная, что : F_n+m = F_m F_n+1 + F_m-1 F_n, запишем рекуррентное соотношение для матричного произведения:

• если m = n, то F_2n = F_n F_n+1 + F_n-1 F_n.

• если m = n + 1, то F_2n+1 = F_n+1 F_n+1 + F_n F_n.

Task

Как известно, последовательность Фибоначчи определяется следующим образом:

F(0) = 0, F(1) = 1, F(n) = F(n – 1) + F(n – 2) (для всех n > 1).

Названа она в честь итальянского математика Леонардо Фибоначчи, известного также под именем Леонардо Пизанского.

Входные данные
Строка содержит целое число n (1 ≤ n ≤ 10¹⁸).

Выходные данные
Вывести значение F(n) вычисленное по модулю 10⁸.

C++

Write a program below
#include <iostream> #include <map> using namespace std; #define MOD 100000000 map<long, long> F; long fib(long n) {

} long a; int main() { scanf("%ld", &a); cout<<fib(a); return 0; }

Your last submission is saved in the editor window.

Results: