Даны целые числа 1≤n≤10^18
и 2≤m≤10^5
, необходимо найти остаток от деления n-го числа Фибоначчи на m.
-
2linux.org.ru/forum/talks/10372353– typemoon7 ноя 2015 в 9:25
-
1А что вы уже пробовали сделать? Что именно не получилось?– Dmitriy Simushev7 ноя 2015 в 9:30
-
1@DmitriySimushev, я могу вычислять относительно небольшие числа Фибоначчи с помощью рекурсии и LUT-метода. Интересует идея для решения задачи описанной в вопросе.– abg7 ноя 2015 в 11:51
Добавить комментарий
|
1 ответ
Решение на 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
-
Очень хорошее решение, кстати. Хотя если бы вы сказали два слова про алгоритм и доказательство корректности, было бы полезнее.– VladD7 ноя 2015 в 12:33
-
Давно хотел отплюсовать. Извлечь ответ из мешка (стека) - такое под силу только настоящему фокуснику! Хотя ответ на вопрос о реальной глубине этого мешка (m? m^2?...), вероятно, останется тайной как для зрителей, так и для фокусника. 12 ноя 2015 в 16:04
-
Тут неплохо объяснили espressocode.top/fibonacci-number-modulo-m-and-pisano-period 18 фев 2021 в 21:38