[백준] 2749 – 피보나치 수 3

문제

2749: 피보나치 수 3 (acmicpc.net)

설명

문제는 N의 범위가 1,000,000,000,000,000,000(사중주 )이라는 것입니다.

잘 알려진 기술인 동적 프로그래밍을 사용하여 해결하기는 어려울 것 같습니다.

피사노 사이클

새로운 개념이 나옵니다.

피사노 사이클은 피보나치 수를 K로 나눌 때 나머지는 항상 점이 있다는 원리나는 아래 표를 보자. 여기서 K는 임의의 숫자를 나타냅니다.

P를 기간의 길이라고 하면 N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M으로 나눈 나머지와 같습니다.

.

그리고 문제는 값을 1,000,000으로 나눈 값을 인쇄하고 M이 $10^{k}$이면 점은 항상 $15×10^{k-1}$입니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<long long> fibo = {0, 1};
    long long p = 1000000 / 10 * 15;
    
    long long N;
    cin >> N;
    
    for (long long i = 2; i < p; i++) {
        fibo.push_back(fibo(i - 1) + fibo(i - 2));
        fibo(i) %= 1000000;
    }
    cout << fibo(N % p);
    
    return 0;
}