Way23
Главная
По категориям
Контакты
Главная
По категориям
Контакты

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

Даны целые числа [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)])
Последниее изменение: 09.07.2025, 06:50