Наибольший общий делитель двух чисел Фибоначчи

Задача

Найти последнюю цифру наибольшего общего делителя двух чисел Фибоначчи.

Решение

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

Воспользуемся свойством чисел Фибоначчиopen in new window:

Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов.

[latex]НОД(F_n, F_m) = F_{НОД(n, m)}[/latex]

Учитвая это вычисляем индекс числа Фибоначчи который одновременно является и нужным НОД, а затем находим его последнее число при помощи периода Пизаноopen in new window.

Сложность

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

Код

На вход подаются два индекса чисел Фибоначчи.

def fib_mod(n, m):
    seq_pisano = find_pisano(m)
    return seq_pisano[n % len(seq_pisano)]

def find_pisano(m):
    pisano = [0, 1]
    n0 = 0
    n1 = 1

    for _ in range(m * 6):
        n0, n1 = n1, (n0 + n1) % m
        pisano.append(n1)

        if pisano[-1] == 1 and pisano[-2] == 0:
            break

    return pisano[:-2]

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

n, m = (int(x) for x in input().split())
f = gcd(n, m)
r = fib_mod(f, 10)
print(r)