1

Даны целые числа 1≤n≤10^18 и 2≤m≤10^5, необходимо найти остаток от деления n-го числа Фибоначчи на m.

3
  • 2
    linux.org.ru/forum/talks/10372353
    – typemoon
    7 ноя 2015 в 9:25
  • 1
    А что вы уже пробовали сделать? Что именно не получилось? 7 ноя 2015 в 9:30
  • 1
    @DmitriySimushev, я могу вычислять относительно небольшие числа Фибоначчи с помощью рекурсии и LUT-метода. Интересует идея для решения задачи описанной в вопросе.
    – abg
    7 ноя 2015 в 11:51

1 ответ 1

7

Решение на Python:

import sys

lineIn = sys.stdin.readline().split(" ")
n = int(lineIn[0])
m = int(lineIn[1])

fibPrev = 0
fib = 1
cached = [fibPrev, fib]

for curr in range(1, n):
    fibOld = fib
    fib = (fib + fibPrev) % m
    fibPrev = fibOld

    if fibPrev == 0 and fib == 1:
        cached.pop()
        break
    else:
        cached.append(fib)

offset = n % len(cached)
sys.stdout.write(str(cached[offset]))

Тест 1:

python ~/Work/python/learning/fibonacci.py
1000000000001 99999
63715
Process finished with exit code 0

Тест 2:

python ~/Work/python/learning/fibonacci.py
100000000000000000000000000001 100
1
Process finished with exit code 0
3
  • Очень хорошее решение, кстати. Хотя если бы вы сказали два слова про алгоритм и доказательство корректности, было бы полезнее.
    – VladD
    7 ноя 2015 в 12:33
  • Давно хотел отплюсовать. Извлечь ответ из мешка (стека) - такое под силу только настоящему фокуснику! Хотя ответ на вопрос о реальной глубине этого мешка (m? m^2?...), вероятно, останется тайной как для зрителей, так и для фокусника. 12 ноя 2015 в 16:04
  • Тут неплохо объяснили espressocode.top/fibonacci-number-modulo-m-and-pisano-period 18 фев 2021 в 21:38

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