[2749] 피보나치 수 3

https://www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

<문제>

피보나치 수를 1'000'000으로 나눈 나머지는 1'500'000의 주기를 갖는다.(피사노 주기)

이에따라 1'500'000번의 반복으로 n번째 피보나치 수를 구할 수 있겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 1000000;
ll n;
int x = 1, y = 1, sum;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    n %= 1500000;
    if (n == 0) {
        cout << 0;
        return 0;
    }
    if (n == 1) {
        cout << 1;
        return 0;
    }
    for (int i = 0; i < n - 2; i++) {
        sum = x + y;
        if (sum > M) sum -= M;
        x = y;
        y = sum;
    }
    cout << y;
    return 0;
}