Python：计算以 m 为模的巨大斐波那契数

Question

# 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 的案例时，需要花费很多时间。您有更好的解决方案吗？

Answer 1

这是我的解决方案，如果找到皮萨诺周期，则不必经历 99999999999999999 次迭代。

我还建议您观看此视频：https://www.youtube.com/watch ?v=Nu-lW-Ifyec

# Uses python3
import sys

def get_fibonacci_huge(n, m):
    if n <= 1:
        return n

    arr = [0, 1]
    previousMod = 0
    currentMod = 1

    for i in range(n - 1):
        tempMod = previousMod
        previousMod = currentMod % m
        currentMod = (tempMod + currentMod) % m
        arr.append(currentMod)
        if currentMod == 1 and previousMod == 0:
            index = (n % (i + 1))
            return arr[index]

    return currentMod

if __name__ == '__main__':
    input = sys.stdin.read();
    n, m = map(int, input.split())
    print(get_fibonacci_huge(n,m))