4.
**Числа Фибоначчи по модулю (С++)
Числа Фибоначчи по модулю
Для эффективного нахождения числа Фибоначчи воспользуемся матричным умножением, подробнее
здесь.
Зная, что
Fn+m=FmFn+1+Fm−1Fn, запишем рекуррентное соотношение для матричного произведения:
• если m=n, то F2n=FnFn+1+Fn−1Fn;
• если m=n+1, то F2n+1=Fn+1Fn+1+FnFn.
Как известно, последовательность Фибоначчи определяется следующим образом:
F(0)=0, F(1)=1, F(n)=F(n–1)+F(n–2), для всех n>1.
Названа она в честь итальянского математика Леонардо Фибоначчи, известного также под именем Леонардо Пизанского.
Входные данные
Строка содержит целое число n (1<=n<=1018).
Выходные данные
Вывести значение F(n), вычисленное по модулю 108.
Вставьте в программу недостающий фрагмент кода.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
30 |
832040 |
Вставьте недостающие фрагменты кода
C++
#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;
}
|