Фибоначчи по модулю

У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 106) человек. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными – они сделали по одному коммиту.

Пусть Fi – число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Первые два стажёра сделали по одному коммиту: F0=F1=1. Для всех i≥ 2 выполнено Fi=Fi−1+Fi−2.

Определите, сколько кода напишет следующий стажёр – найдите последние k цифр числа Fn.


Как найти k последних цифр

Чтобы вычислить k последних цифр некоторого числа x, достаточно взять остаток от его деления на число 10k. Эта операция обозначается как x mod 10k. Узнайте, как записывается операция взятия остатка по модулю в вашем языке программирования.

Также обратите внимание на возможное переполнение целочисленных типов, если в вашем языке такое случается.

Формат ввода

В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 106) и k (1 ≤ k ≤ 8).

Формат вывода

Выведите единственное число – последние k цифр числа Fn.

Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.



n, k = (int(i) for i in input().split())
ab = [1, 1]
d=(10 ** k)
if n < 2:
    fib = 1
else:
    n -= 1
    for i in range(n):
        s = (ab[0] + ab[1]) % d
        ab[0] = ab[1]
        ab[1] = s
        fib = ab[1]
print(fib)


Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: