結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
|
提出日時 | 2020-10-24 13:54:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 573 bytes |
コンパイル時間 | 84 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-07-21 15:13:12 |
合計ジャッジ時間 | 1,251 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
N, M = map(int, input().split()) if N < 3: print(N-1) exit() N -= 2 a, b, c, d = [1, 0, 0, 1] na, nb, nc, nd = [1, 1, 1, 0] while N > 0: if N % 2 > 0: a, b, c, d = [na*a % M+nb*c % M, na*b % M + nb * d % M, a * nc % M + c * nd % M, d * nd % M + b * nc % M] a %= M b %= M c %= M d %= M na, nb, nc, nd = [na*na % M+nb*nc % M, na*nb % M + nb * nd % M, na * nc % M + nc * nd % M, nd * nd % M + nb * nc % M] na %= M nb %= M nc %= M nd %= M N //= 2 print(a)