python-3.x - Python:计算巨大的斐波那契数模

# Uses python3
# Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m
def Huge_Fib(n,m):

    if n == 0 : return 0
    elif n == 1: return 1
    else:
        a,b = 0,1
        for i in range(1,n):
            a, b = b, (a+b) % m
        print(b);

n,m = map(int, input().split());
Huge_Fib(n,m);

该代码运行良好。但是，当我运行n = 99999999999999999，m = 2的案例时，这需要花费很多时间。您有更好的解决方案吗？

最佳答案

# Uses python3
# Given two integers n and m, output Fn mod m (that is, the remainder of Fn when divided by m
def Huge_Fib(n,m):

    # Initialize a matrix [[1,1],[1,0]]
    v1, v2, v3 = 1, 1, 0
    # Perform fast exponentiation of the matrix (quickly raise it to the nth power)
    for rec in bin(n)[3:]:
        calc = (v2*v2) % m
        v1, v2, v3 = (v1*v1+calc) % m, ((v1+v3)*v2) % m, (calc+v3*v3) % m
        if rec == '1': v1, v2, v3 = (v1+v2) % m, v1, v2
    print(v2);

n,m = map(int, input().split());
Huge_Fib(n,m);

这是一个超快速的解决方案，请参考https://stackoverflow.com/a/23462371/3700852

关于python-3.x - Python:计算巨大的斐波那契数模，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40096097/