백준(baekjoon)(BaekJoon)코딩 2749번:피보나치 수열(3) 답

#include <iostream>
using namespace std;
const int mod = 1000000;
const int p = mod/10*15;//피보나치 수열은 일정한 주기를 가진다
int fibo[p] = {0,1};
int main() {
    long long n;
    cin >> n;
    for (int i=2; i<p; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
        fibo[i] %= mod;
    }
    cout << fibo[n%p] << '\n';
    return 0;
}