[백준/C++] 피보나치 수 3

문제

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

---

문제 요약

n이 주어졌을 때, 피보나치 수열에서 n번째 수를 1,000,000으로 나눈 출력한다.

 

n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

---

코드

#include <iostream>

# define ll long long

using namespace std;

ll n;

ll dp[2000020];

ll fibo(int num) {
    if (dp[num] != -1) return dp[num];

    return dp[num] = (fibo(num - 1) + fibo(num - 2)) % 1000000;
}

int main() {
    cin >> n;

    for (int i = 0; i < 2000020; i++) {
        dp[i] = -1;
    }

    dp[0] = 0;
    dp[1] = 1;

    cout << fibo(n % 1500000);
    
    return 0;
}

---

코드 설명

https://daily-program-ing.tistory.com/287

 

위 문제에서 피사노 주기(피보나치 수열을 m으로 나눈 나머지로 이루어진 수열의 주기)를 알 수 있다.

 

따라서, 피보나치 수열을 1,000,000으로 나눈 나머지로 이루어진 수열의 주기를 알 수 있다.

 

위 출력 결과에서 피보나치 수를 1,000,000으로 나눈 나머지로 이루어진 수열의 주기가 1,500,000임을 알 수 있다.

 

따라서 n번째 피보나치 수는 n % 1,500,000번째 피보나치 수와 같다.