Поиск периода Пизано
Даны целые числа [latex]1 \leq n \leq 10^{18}[/latex] и [latex]2 \leq m \leq 10^5[/latex], необходимо найти остаток от деления n-го числа Фибоначчи на m.
Решение
Последовательность остатков при делении чисел Фибоначчи на натуральное число периодична. Период Пизано - это длина периода этой последовательности.
Для нахождения остатка от деления n-го числа Фибоначчи на натуральное число m достаточно найти все числа периода Пизано для данного m, затем найти остаток от деления n на длину периода, и взять число из периода Пизано под этим номером.
Саму последовательность Фибоначчи можно не вычислять, для нахождения периода использовать только остатки.
Первые числа в периоде Пизано - 0 и 1. Длина периода не больше m * 6 (доказательство этого не нашёл).
n, m = [int(x) for x in input().split()]
def find_pisano(n, m):
pisano = []
pisano.append(0)
# при делении на 1 остаток будет всегда 0
if m == 1:
return pisano
pisano.append(1)
# при m > 0 остатки от деления первого и второго числа Фибоначчи
# всегда 0 и 1
if n <= 1:
return pisano
n0 = 0
n1 = 1
for __ in range(m * 6):
# для ускорения не вычисляем числа Фибоначчи полностью
# берём только остатки по модулю m
n0, n1 = n1, (n0 + n1) % m
pisano.append(n1 % m)
# Проверяем не начался ли новый период
# период всегда начинается с 0 и 1
if pisano[len(pisano) - 1] == 1 \
and pisano[len(pisano) - 2] == 0:
break
return pisano[:-2]
pisano = find_pisano(n, m)
print(pisano)
print(pisano[n % len(pisano)])