Поиск периода Пизано

Даны целые числа \(1 \leq n \leq 10^{18}\) и \(2 \leq m \leq 10^5\), необходимо найти остаток от деления n-го числа Фибоначчи на m.

Решение

Последовательность остатков при делении чисел Фибоначчи на натуральное число периодична. Период Пизано — это длина периода этой последовательности.

Для нахождения остатка от деления n-го числа Фибоначчи на натуральное число m достаточно найти все числа периода Пизано для данного m, затем найти остаток от деления n на длину периода, и взять число из периода Пизано под этим номером.

Саму последовательность Фибоначчи можно не вычислять, для нахождения периода использовать только остатки.

Первые числа в периоде Пизано — 0 и 1. Длина периода не больше m * 6 (доказательство этого не нашёл).

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *