1г

Помогите с задачей

Числа Фибоначчи это последовательность целых чисел, заданная рекуррентным соотношением: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2, n ≥ 2.
Ваша задача найти наибольший общий делитель двух чисел Фибоначчи.
Формат входного файла
Во входном файле два числа i и j (1 ≤ i, j ≤ 106) номера чисел Фибоначчи
Формат выходного файла
В выходной файл выведите остаток от деления наибольшего общего делителя чисел Fi и Fj на 109.

С помощью def

По дате

По Рейтингу

papa_1085

Новичок

1г

В лоб это решается так:

12345678910111213141516171819

 def gcde(a, b):
    while a:
        a, b = b % a, a
    return b

def gcdfib(i, j):
    if i > j: i, j = j, i
    f1, f2 = 0, 1
    while i:
        f1, f2 = f2, f1 + f2
        i -= 1; j -= 1
    fi = f1
    while j:
        f1, f2 = f2, f1 + f2
        j -= 1
    fj = f1
    return gcde(fi, fj)

print(gcdfib(*map(int, map(input, ('',) * 2))) % 1000000000)

Об именах файлов и формате данных ничего не сказано, поэтому числа вводим со стандартного ввода, каждое число на отдельной строке, результат выводим в стандартный вывод.

Но вообще говоря, НОД(Fi, Fj) = F(НОД(i, j)), поэтому всё можно решить проще:

123456789101112131415

 def gcde(a, b):
    while a:
        a, b = b % a, a
    return b

def gcdfib1(i, j):
    if i > j: i, j = j, i
    g = gcde(i, j)
    f1, f2 = 0, 1
    while g:
        f1, f2 = f2, f1 + f2
        g -= 1
    return f1

print(gcdfib1(*map(int, map(input, ('',) * 2))))

shi_143

Оракул

1г

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556

 # Функция для вычисления n-го числа Фибоначчи 
def fibonacci(n): 
    # Проверяем, что n неотрицательное целое число 
    if type(n) != int or n < 0: 
        return "Неверный ввод" 
    # Инициализируем первые два числа Фибоначчи 
    a = 0 
    b = 1 
    # Если n равно 0 или 1, возвращаем его же 
    if n == 0 or n == 1: 
        return n 
    # Иначе итеративно вычисляем n-е число Фибоначчи 
    for i in range(2, n + 1): 
        c = a + b # Суммируем два предыдущих числа 
        a = b # Обновляем a 
        b = c # Обновляем b 
    return c # Возвращаем n-е число Фибоначчи 
 
# Функция для вычисления НОД двух целых чисел с помощью алгоритма Евклида 
def gcd(a, b): 
    # Проверяем, что a и b положительные целые числа 
    if type(a) != int or type(b) != int or a <= 0 or b <= 0: 
        return "Неверный ввод" 
    # Если a меньше b, меняем их местами 
    if a < b: 
        a, b = b, a 
    # Пока b не равно нулю, повторяем следующие шаги: 
    while b != 0: 
        # Находим остаток от деления a на b 
        r = a % b 
        # Присваиваем a значение b 
        a = b 
        # Присваиваем b значение r 
        b = r 
    # Возвращаем a как НОД 
    return a 
 
# Функция для решения задачи поиска остатка от деления НОД двух чисел Фибоначчи на 10^9 
def solve(i, j): 
    # Проверяем, что i и j положительные целые числа не больше 10^6 
    if type(i) != int or type(j) != int or i <= 0 or j <= 0 or i > 10**6 or j > 10**6: 
        return "Неверный ввод" 
    # Вычисляем i-е и j-е числа Фибоначчи с помощью функции fibonacci 
    fi = fibonacci(i) 
    fj = fibonacci(j) 
    # Вычисляем НОД fi и fj с помощью функции gcd 
    g = gcd(fi, fj) 
    # Вычисляем остаток от деления g на 10^9 с помощью оператора % 
    r = g % (10**9) 
    # Возвращаем r как ответ 
    return r 
 
# Пример использования функции solve 
print(solve(10, 15)) # Выводит 1 
print(solve(100, 200)) # Выводит 6765