2

Помогите, пожалуйста, понять в чём ошибка.

Как известно, последовательность Фибоначчи определяется следующим образом:

F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2) (для всех n > 1). По заданным n и m вычислить самый общий делитель чисел F(n) и F(m).

Вводимые данные данные: Каждая строка является отдельным тестом и содержит два целых числа n и m (1 ≤ n, m ≤ 10^18). Число тестов не превышает 1000

Исходные данные: Для каждого теста в отдельной строке вывести значение НОД(F(n),F(m)), вычисленное по модулю 10^8.

Вводимые данные :                                        Исходные данные:
2 3                                                      1
1 1                                                      1
100 200                                                  61915075

Ссылка на задание (там можно проверить правильность кода(на украинском языке))

Во-первых, программа точно не будет проходить по времени. Можно ли как-то её ускорить? Во-вторых, сайт с заданием наотрез не хочет принимать код, то есть, не проходит ни один из тестов. Пытался разобраться с правильностью вводом данных несколько часов, и ни к чему не пришёл, кроме как к while True

Вот мой код :

import math
def fibonacci(n):
    fib1 = 1 #0 1 1 2 3 5 8 13 21 34
    fib2 = 1
    i = 0
    while i < n - 2:
        fib_sum = fib1 + fib2
        fib1 = fib2
        fib2 = fib_sum
        i = i + 1
    return fib2
cou=0
while True:
    m, k = map(int, input().split())
    print(math.gcd(fibonacci(m), fibonacci(k)) % 10**8)
1
  • 1
    программа точно не будет проходить по времени. Можно ли как-то её ускорить? Да запросто. Просто не надо вычислять каждый раз число с самого начала...
    – Akina
    9 ноя 2021 в 16:04

3 ответа 3

4

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

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 раз!

2
  • Здравствуйте, огромное спасибо за проделанный труд. Второй раз уже мне помогаете, искренне благодарю! Задачка, конечно, сбивает меня с толку , человека, изучающего python всего 2 месяца))) 9 ноя 2021 в 21:14
  • Пожалуйста. Но задача не про Питон. Задача про свойства чисел Фибоначчи. :) 9 ноя 2021 в 21:52
4

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

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

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

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

9
  • К вашему решению ещё добавить вычисление F(n) сразу по модулю 10^8 и задача будет решена за одну секунду даже на Питоне. 9 ноя 2021 в 16:42
  • Сегодня вечером на e-olymp будет решение на Питоне. :) 9 ноя 2021 в 16:43
  • @StanislavVolodarskiy, ждём с нетерпением :)
    – Sunny Cove
    9 ноя 2021 в 16:44
  • @StanislavVolodarskiy, мне не доводилось писать вычисление больших Фибоначчи, и сейчас не очень много времени на подобные затеи, так что будет здорово, если Вы реализуете
    – Sunny Cove
    9 ноя 2021 в 16:48
  • 1
2

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

  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]
  1. возможно нельзя использовать библиотечные функции и надо написать свою функцию НОД:

код:

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

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

  1. если не использовать матричный способ нахождения чисел Фибоначчи, то тогда 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
1
  • 1
    F(10^18) - очень длинное число. Считать надо по модулю. 9 ноя 2021 в 16:36

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.