피보나치 수 3 <백준 2749번 문제>

문제 출처: https://www.acmicpc.net/problem/2749 

※공식※

피보나치 수를 나눌 수를 K라고 할 때,

이면, 피사노 주기는 

 

 

2749번 문제의 출력 조건은 “n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력합니다." 인데, 피보나치 수를 나눈 나머지들은 반드시 주기를 가지며, 이를 피사노 주기라고 한다는 사실을 알게 되었다.1 2 위 내용을 참고해 2749번 문제를 풀면서 사용한 정의는 다음과 같습니다.

---

피보나치 수를 나눌 수를 K라고 할 때, k=10^n 이면, 피사노 주기는 15∗10^n−1이다.

---

문제에서 106106 으로 나눈 나머지를 구하라고 했으므로 주기는 1,500,000 이 된다는 것을 알 수 있습니다.

따라서 입력의 최대값이 1,000,000,000,000,000,000 이더라도, 최대 1,500,000번째 까지만 106106로 나눈 나머지 값들을 알면 그 이후의 위치는 따로 계산할 필요가 없게 됩니다.