Вопрос:
Целью этой задачи является вычисление F [n] mod m. Здесь входы представляют собой n и m, где n обозначает индекс числа фибоначчи, скажем F [0] = 0, F [1] = 1, F [2] = 1, F [3] = 2 и m стоит для числа, на которое F [n] будет разделено. Ограничения:
- n> = 1 и n <= 10 18
- m> = 2 и m <= 10 ^ 5
До сих пор я дошел до этой проблемы и смог получить точный результат этой проблемы, за исключением случаев, когда я даю 100000 в качестве значения m, это превышает срок. Срок составляет 5 секунд. Если значение m задано между и от 2 до 99999, моя программа генерирует правильный выход в течение срока. Любая помощь в решении этой проблемы была бы высоко оценена.
Код:
def fibonacci(n): if ( n == 0 ): return (0, 1) else: a, b = fibonacci(n/2) c = a * (2* b — a) d = a**2 + b**2 if ( n % 2 ): return (d, c + d) else: return (c, d) def findRemainders(m): remainderList = [«0», «1»] i = 2 while(1): firstFib, secondFib = fibonacci(i) if ( (firstFib % m) == 0 and (secondFib % m) == 1 ): break remainderList.append( (firstFib % m) ) remainderList.append( (secondFib % m) ) i += 2 return remainderList def hugeFibonacciNumberModulo_m( n, m ): remainderList = findRemainders(m) length_of_period = len(remainderList) remainder = (n % length_of_period) out = remainderList[remainder] return out inp = map(int, raw_input().split()) n, m = inp[0], inp[1] if ( (n >= 1 and n <= 10**18) and (m >= 2 and m <= 10**5) ): out = hugeFibonacciNumberModulo_m( n, m ) print out Лучший ответ:
Я не понимаю, что вы пытаетесь сделать в findRemainders(m) или зачем вам это нужно. Вы уже используете алгоритм Фибоначчи по удвоению, который аналогичен алгоритму матрица-экспоненциация по квадрату (и обычно получается из него). Экспоненциальность может быть изменена, чтобы эффективно обрабатывать модульное возведение в степень, по существу модифицируя ваши частичные результаты (результаты) на каждом шаге.
def fibmod(n, m): assert 1 <= n <= 10**18, n assert 2 <= m <= 10**5, m def f(n): if n == 0: return 0, 1 else: a, b = f(n // 2) c = a * (2*b — a) % m d = (a**2 + b**2) % m if n % 2 == 0: return c, d else: return d, (c + d) % m return f(n)[0]
Вы можете еще раз разбить выражение для c и d и применить % m после каждого промежуточного умножения, сложения и вычитания для предотвращения переполнения (но это не проблема Python).
Ответ №1
Вы можете сделать это очень быстро, используя модульное возведение в степень.
Рассмотрим следующее умножение матрицы:
| 0 1 | | a | | b | | | x | | = | | | 1 1 | | b | | a+b |
Вы должны сразу увидеть, что результатом этого умножения является следующая итерация последовательности Фибоначчи, если a и b являются последними двумя членами. Чтобы получить результат выполнения этого умножения n раз, вам нужно вычислить n-th степень матрицы 2×2 (0,1;1,1) (mod m). Это можно сделать очень быстро, подняв эту матрицу до последовательных степеней 2.
Например, чтобы вычислить 10-ю степень этой матрицы:
| 0 1 | | 0 1 | | 1 1 | A x A = A**2 = | | x | | = | | | 1 1 | | 1 1 | | 1 2 | | 1 1 | | 1 1 | | 2 3 | A**4 = (A**2)**2 = | | x | | = | | | 1 2 | | 1 2 | | 3 5 | | 2 3 | | 2 3 | | 13 21 | A**8 = (A**4)**2 = | | x | | = | | | 3 5 | | 3 5 | | 21 34 |
После квадратичной матрицы три раза мы теперь имеем значения A**8 и A**2. Умножьте их вместе, и вы получите A**10:
| 13 21 | | 1 1 | | 34 55 | A**10 = | | x | | = | | | 21 34 | | 1 2 | | 55 89 |
Эти цифры быстро станут огромными в обычной арифметике, но если вы выполняете все свои умножения по модулю m, то это не проблема. Наконец, умножьте вектор (0; 1) на полученную матрицу, чтобы получить ответ (или, что то же самое, просто выберите второе число в верхней строке матрицы).
Количество требуемых умножений составляет порядка log(n), поэтому требуемое время должно быть очень маленьким, даже если m равно триллиону или больше.
См. Википедию для получения дополнительной информации о модульном экспонировании матриц.
