Задача 76206

Темы:    [ Числа Фибоначчи ] [ Линейная алгебра ]

Сложность: 4 Классы:

Условие

Та же задача, если требуется, чтобы число операций было пропорционально log n. (Переменные должны быть целочисленными.)

Подсказка

Пара соседних чисел Фибоначчи получается из предыдущей умножением на матрицу

 

-- так что задача сводится к возведению матрицы в степень n. Это можно сделать за C log n действий тем же способом, что и для чисел.

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	1
Название	Задачи без массивов
задача
Номер	1.1.10