Функция Эйлера и другие задачи теории чисел




№ 9/9 **Числа Фибоначчи по модулю (С++)

Read Theory

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

зная, что : Fn+m = Fm Fn+1 + Fm-1 Fn, запишем рекуррентное соотношение для матричного произведения:
• если m = n, то F2n = Fn Fn+1 + Fn-1 Fn.
• если m = n + 1, то F2n+1 = Fn+1 Fn+1 + Fn Fn.
 

Task
Как известно, последовательность Фибоначчи определяется следующим образом:
F(0) = 0, F(1) = 1, F(n) = F(n – 1) + F(n – 2) (для всех n > 1).
Названа она в честь итальянского математика Леонардо Фибоначчи, известного также под именем Леонардо Пизанского.
 
Входные данные
Строка содержит целое число n (1 ≤ n ≤ 1018).
 
Выходные данные
Вывести значение F(n) вычисленное по модулю 108.

 
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:

All results:

©2009 - 2019 SilverTests.ru/en

Education

Quizes
Problems
Courses

My Account

Register
Sign

About us

Contacts
Rules