백준 2749 피보나치 수 3(피사노 주기)

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

 

blog.naver.com/PostView.nhn?blogId=richard0326&logNo=221142014183&categoryNo=83&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

피사노 주기(Pisano Period)

피보나치 수를 임의의 수 K로 나누게 되면 무조건 주기를 갖는다. 

 

만약 10^K의 수로 나누게 되면 주기 p의 값은 무조건 15*10^(K-1)이 된다.

 

따라서 만약 문제에서 10의 거듭제곱 꼴로 나눈 값을 구하라고 하면 이걸 이용해서 쉽게 구할 수 있다 그게 아니면 그냥 거듭제곱으로 구하면 될듯? 

 

 

#include<iostream>
using namespace std;
#define MOD 1000000
const int p = MOD / 10 * 15;
typedef long long ll;

int fibo[p] = { 0,1 };

int main() {
	ll 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];
}