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

풀이

---

피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 된다. 이를 피사노 주기(Pisano Period)라고 한다.

피보나치 수를 3으로 나누었을 때 주기는 8이 된다.

 

이 때, 주기의 길이가 P라면:

    N번째 피보나치 수를 K로 나눈 나머지 == N%P번째 피보나치 수를 K로 나눈 나머지

 

 

 

코드

---

C++ 언어를 이용해 코드를 살펴보자.

#include <iostream>
using namespace std;
 
// 주기를 구하는 공식
// 피보나치 수를 M으로 나눈 나머지를 구하는 문제에서 나머지는 주기를 가지게 된다. ('파사노 주기'라고 한다.)
// M = 10^k일 때, k>2라면 주기는 15 * 10^(k-1)
constexpr int MOD = 1000000; 
constexpr int P = (MOD / 10) * 15; // M=10^6이니 주기는 15*10^5가 된다.
 
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;
}

 

 

 

참고자료

---

[1] https://www.acmicpc.net/blog/view/28