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

# 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

Answer 2

ピサノの期間を調べる必要があります。 https://en.wikipedia.org/wiki/Pisano_periodと http://webspace.ship.edu/msrenault/fibonacci/fibfactory.htmは、それらが何であるかをよく理解しておく必要があります。

編集：ちょうどグーグル "フィボナッチモジュロ"は、上位2つの結果としてそれら2つを与えます。

Answer 3

を参照してくださいが、私の解決策である超高速ソリューションである、あなたがピサーノ期間を見つけた場合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))