在 O(1) 时间内找到斐波那契数列特定索引处的单位数字。 （斐波那契数列可能 <=10^18）
To find unit digit at a particular index of fibonacci series in O(1) time. (fibonacci series may be <=10^18)
此代码在输入超过 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)
斐波那契数列的个位数为 60 的循环（无需深入地图，您可以看到在 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]
和 return fib_digit[N % 60] 在 O(1) 中。
此代码在输入超过 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)
斐波那契数列的个位数为 60 的循环（无需深入地图，您可以看到在 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]
和 return fib_digit[N % 60] 在 O(1) 中。