結果

問題 No.526 フィボナッチ数列の第N項をMで割った余りを求める
コンテスト
ユーザー shuichi fujii
提出日時 2025-08-30 13:33:58
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 550 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2025-08-30 13:34:00
合計ジャッジ時間 1,559 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

def mul_matrix(A, B, M):
    a, b = A[0]
    c, d = A[1]
    e, f = B[0]
    g, h = B[1]
    return [
        [(a*e + b*g) % M, (a*f + b*h) % M],
        [(c*e + d*g) % M, (c*f + d*h) % M],
    ]



N, M = map(int, input().split())

if N == 1:
    print(0)
    exit()

elif N == 2:
    print(1)
    exit()
    
plus = [
    [1, 1], 
    [1, 0]
]

base = [
    [1, 0], 
    [0, 1]
]

exp = N - 2

while exp > 0:
    if exp & 1:
        base = mul_matrix(base, plus, M)
        
    plus = mul_matrix(plus, plus, M)
    exp >>= 1
    
print(base[0][0])
0