python-3.x - 在 O(1) 时间内找到斐波那契数列特定索引处的单位数字。 (斐波那契数列可能 <=10^18)

Question

这段代码给出了超过 10^7 输入的错误输出。任何人都可以帮我解决这个问题吗？

from math import sqrt,floor,log
def fib(N):
    var = (1 + sqrt(5)) / 2
    return round(pow(var, N) / sqrt(5))


test = int(input())

a=floor(log(test,2))
b=2**a
a=b%60
print(fib(a-1)%10)

Answer 1

斐波那契数列的个位数为 60 的循环(无需深入 map ，您可以看到在 60 之后您再次得到 1 和 1，因此总和为 2，依此类推)。因此，您可以准备一个包含这些斐波那契数位的列表:

fib_digit = [1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0]

并在 O(1) 中返回 fib_digit[N % 60]。