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

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

Решение

Последовательность остатков при делении чисел Фибоначчи на натуральное число периодична. Период Пизаноopen in new window - это длина периода этой последовательности.

Для нахождения остатка от деления 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)])