НОД чисел Фибоначчи

Что можно предложить

1. использовать матричный способ вычисления числа Фибоначчи:

код:

def pow(x, n, I, mult):
    if n == 0:
        return I
    elif n == 1:
        return x
    else:
        y = pow(x, n // 2, I, mult)
        y = mult(y, y)
        if n % 2:
            y = mult(x, y)
        return y


def identity_matrix(n):
    r = list(range(n))
    return [[1 if i == j else 0 for i in r] for j in r]


def matrix_multiply(A, B):
    BT = list(zip(*B))
    return [[sum(a * b
                 for a, b in zip(row_a, col_b))
            for col_b in BT]
            for row_a in A]


def fib(n):
    F = pow([[1, 1], [1, 0]], n, identity_matrix(2), matrix_multiply)
    return F[0][1]

2. возможно нельзя использовать библиотечные функции и надо написать свою функцию НОД:

код:

def _gcd(a, b):
    while a != 0 and b != 0:
        if a > b:
            a = a % b
        else:
            b = b % a

    return a + b

или

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a

    return a

надо посмотреть какой из двух способов работает побыстрее

3. если не использовать матричный способ нахождения чисел Фибоначчи, то тогда 2 числа можно вычислить за 1 проход, ведь одно число меньше второго и значит во время цикла оно тоже будет найдено

для этого можно использовать такой код:

def fib(n):
    a = 0
    b = 1
    for __ in range(n):
        a, b = b, a + b
    return a

, вернее его модификацию:

def fib(n1, n2):
    a = 0
    b = 1
    first = 0
    for i in range(n2):
        a, b = b, a + b
        if i == n1:
            first = a
    return first, a

Можно воспользоваться той простой идеей, что НОД двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным НОД их индексов (взято с Википедии). Для поиска же n-го числа Фибоначчи по индексу эффективный алгоритм Вам уже предложил @Zhihar.

Также хочу добавить, что интерпретатор Питона – штука достаточно медленная, и не всегда на подобных сайтах гарантируется, что существует решение на Питоне, которое пройдёт по времени; обычно обещают, что такое решение существует на C/C++. В данной задаче требуется вычислить нужное число в худшем случае за 1 мс (1 секунда, 1000 разных больших тестов), и не факт, что есть решение, которое уложится в ограничения.

Кроме того, рекомендую использовать PyPy для скриптов на Питоне в тестирующей системе (если он доступен), особенно для вычислительных задач – в некоторых случаях он существенно ускоряет за счёт предварительной компиляции.

UPD: Спасибо за плюсы, но этот ответ здесь скорее в роли дополнения, чем решения. Заслуженно они должны достаться подробному объяснению @Stanislav Volodarskiy, на мой взгляд :)

Ввод без счётчика можно сделать так:

import sys

for line in sys.stdin:
    n, m = map(int, line.split())
    ...

Других ошибок в коде я не вижу. Трудность только со временем работы. Долго ли будет вычисляться fibonacci(10 ** 18)? Если ваш компьютер делает один миллиард итераций цикла в секунду (а он работает медленнее, но всё же), то вам нужно 10^18 / 10^9 секунд = 32.5 года.

Даже если вы готовы ждать 33 года (33000 лет для тысячи тестов), у вас нет достаточно памяти чтобы хранить fibonacci(10 ** 18). По формуле Бине оценим число бит для этого числа: 10**18 * log2((1 + sqrt(5)) / 2) = 6.9e+17 бит = 80820396 Gb.

Плохие новости кончились.

В ответе Sunny Cove есть ключевая идея решения: НОД(fib(n), fib(m)) = fib(НОД(n, m)). Смотрите свойства чисел Фибоначчи.

Нам нужно посчитать fib(n) для числа n <= 10^18. Хотя НОД уже вычислен, он может быть равен большему из чисел. В этом смысле задача проще не стала. В уже упомянутых свойствах есть интересное матричное равенство:

/ 1 1 \ n   / fib(n+1) fib(n)   \
|     |   = |                   |
\ 1 0 /     \ fib(n)   fib(n-1) /

Числа Фибоначчи можно считать как степень матрицы. А степень матрицы считается с помощью быстрого возведения в степень.

Так как нам нужно не само число Фибоначчи а остаток по модулю, то все операции во время возведения в степень тоже будем делать по модулю. Это гарантирует что все числа в вычислениях будут фиксированного размера. Это даст скорость и малое потребление памяти.

Собирая всё вместе:

import math
import sys


# a     = F[n     - 1], F[n    ], F[n     + 1]
# b     = F[    m - 1], F[    m], F[    m + 1]
# a * b = F[n + m - 1], F[n + m], F[n + m + 1]
def mul_mod(a, b, m):
    return (
        (a[0] * b[0] + a[1] * b[1]) % m,
        (a[0] * b[1] + a[1] * b[2]) % m,
        (a[1] * b[1] + a[2] * b[2]) % m
    )


def pow_mod(a, b, m):
    if b == 0:
        return 1, 0, 1
    if b % 2 == 0:
        q = pow_mod(a, b // 2, m)
        return mul_mod(q, q, m)
    return mul_mod(a, pow_mod(a, b - 1, m), m)


def fib_mod(n, m):
    return 0 if n == 0 else pow_mod((0, 1, 1), n - 1, m)[-1]


for line in sys.stdin:
    n, m = map(int, line.split())
    g = math.gcd(n, m)
    print(fib_mod(g, 10 ** 8))

P.S. Эта программа прошла все тесты на e-olymp. Худшее время теста - 173ms. Покопавшись можно найти решение на Питоне в пять раз (!) быстрее - 36ms. Есть куда стремиться, если учесть что программа читающая и пишущая тысячу строк работает около 26ms. 10ms на вычисления! Вычислительная часть работает быстрее чем моя в 15 раз!