백준_피보나치 3_2749(java)

피보나치 3

1. 문제

https://www.acmicpc.net/problem/2749

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

단순하게 나머지를 구한다고 생각하면 안풀린다.

피보나치수에서 나머지의 주기가 있음을 알아야 한다.... 아니 왜 다 .... 하나같이 쉬운게 없냐,,,

피보나치 수를 나눈 나머지들은 반드시 주기를 가지며, 이를 피사노 주기라고 부른다.

이때의 10의 n승은 나누는 수를 의미

K(M)은 M으로 나눈 주기를 의미

주기의 길이가 P 이면, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같습니다.

solution - 1) 

1,000,000 = 10의 6승 

=> 15 * 10의 5승 = 1,500,000길이의 주기를 가진다.

1000번째 피보나치 수를 1,000,000으로 나눈 나머지는

1000%1,500,000%M을 구하면 된다구...?

로 했는데 계속 런타임 에러나서 멘붕,,,,

아래 링크 참조해보자,,,

https://nackwon.tistory.com/52