백준 2749 피보나치 수 3 (C++)

2749번: 피보나치 수 3

피사노 주기라는 공식을 이용하는 문제이다. 피보나치 수를 구하는 공식 중 피사노 주기라는 공식이 있다. 피보나치 수를 특정 값으로 나눌 때 항상 일정 주기를 가지게 되는데 이를 피사노 주기라고 한다. 공식은 다음과 같다.

• 주기의 길이를 P라고 할 때, N번째 피보나치 수를 특정 값 M으로 나눈 나머지는 N % P번째 피보나치 수를 M으로 나눈 나머지와 같다.
• 주기는 M = 10^k (k>2)일 때, 항상 15 * 10^(k-1) 이다.

이를 문제에 응용하게 되면 1,000,000으뢰 나눈 나머지를 구해야 하므로 M = 1,000,000이 되고 주기 공식을 통해 P = 15 * 10^5가 된다. P 주기까지 반복문을 돌며 피보나치 수의 나머지를 구한 후 n % P번째 피보나치 수의 나머지를 출력해주었다. 피사노 주기라는 공식을 처음 알게 되었다. 피보나치 수는 단순히 재귀나 동적 계획법을 이용하여 푸는 법만 알고 있었는데 새로운 공식을 알게 되어 흥미로웠다. 피사노 주기에 대해 기억해두어야 겠다.

#include <iostream>

#define P 1500000

using namespace std;

long long n;
int a[P];

void solution() {
	if (n == 0) cout << "0";
	else if (n == 1) cout << "1";
	else {
		a[0] = 0;
		a[1] = 1;

		// 1,000,000 = 10^6이므로 주기는 15 * 10^5
		for (int i = 2; i < P; i++) {
			a[i] = (a[i - 2] + a[i - 1]) % 1000000;
		}

		cout << a[n % P];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;

	solution();
	
	return 0;
}