フィボナッチ数列の第N項をMで割った余りを求める [yukicoder No.526]

http://yukicoder.me/problems/no/526

解説放送

https://youtu.be/ouZhINpOJys?t=207

解法

http://yukicoder.me/submissions/179064
フィボナッチ数列を愚直にもとめていけば良い。
普通に計算していると計算過程でオーバーフローしてしまうので、適宜mod Mを取る。

typedef long long ll;
int N, M;
ll F[5010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    F[1] = 0;
    F[2] = 1;
    rep(i, 3, N + 1) {
        F[i] = (F[i - 1] + F[i - 2]) % M;
    }
    cout << F[N] << endl;
}