結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
![]() |
提出日時 | 2021-04-26 20:29:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 667 bytes |
コンパイル時間 | 1,419 ms |
コンパイル使用メモリ | 173,272 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-05 06:27:57 |
合計ジャッジ時間 | 2,107 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; map<long long,long long> fib; long long fibonacci(long long N,long long mod){ if(fib[N]!=0) return fib[N]; if(N==0) return fib[N] = 0; if(N==1 || N==2) return fib[N] = 1; if(N%2==0){ return fib[N] = (((fibonacci(N/2+1,mod) * fibonacci(N/2,mod)) % mod) + (fibonacci(N/2,mod) * fibonacci(N/2-1,mod)) % mod) % mod; }else if(N%2==1){ return fib[N] = (((fibonacci((N+1)/2,mod) * fibonacci((N+1)/2,mod)) % mod) + (fibonacci((N-1)/2,mod) * fibonacci((N-1)/2,mod)) % mod) % mod; } return -1; } int main(){ long long N,M; cin >> N >> M; cout << fibonacci(N-1,M) << endl; }