[AC]2749 피보나치수3

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2749.cpp

오늘 정확히는 어제 공부한 내용은 피사노주기이다. 2일이나 공부했는데 이해가 쉽게 가지 않았다.

먼저 문제는 피보나치수를 구하는데 10^18이 최대 인풋이다. 단순 포문으로는 절대 답을 구하지 못한다.
(그 전에 공부한 최소값문제도 단순 탐색으로는 구하지 못하는 문제였다.)

많은 고민을 해보다가 도무지 해결책이 떠오르지 않아, 검색을 하였다. 그리고 알게된 것이 피사노주기(pisano period)이다.

바로 다음문제(9471)에 피사노 주기에 대한 설명이 있기에, 설명은 스킵하고 문제의 해결법을 적겠다.

먼저 피보나치에서 변하지않는 진리가 있다면 이전 2개의 수를 가지고 현재 값이 나온다는 것이다. 그리고 현재 문제는 1,000,000으로 나눈 값을 출력하라고 하였다. 이게 포인트인것이다.

피사노주기의 규칙에 의하면 피보나치수를 m으로 나누면 반드시 주기가 생긴다고 한다. 주기가 있다면 수들은 반복이 된다.

즉, 주기만 찾는다면 불필요한 연산을 전부 제외하고 딱 그만큼만 계산하면 된다.

이문제에서 m은 1,000,000이라고 하였으니  피사노 주기 규칙에 의해 n > 2라면, k(10n) = 15×10(n-1)이 성립하게 된다.

그럼 1,000,000은 10^6이므로 15*10^(6-1) 이므로 1500000이 된다. 이렇게 간단하게 주기를 찾았다. 이제 주기로 나눠주기만 하면 된다. 그래서 포문을

for (int i = 1; i < n%pisano; i++)

이렇게 표현하였는데 입력된 n값에 피사노주기로 나눠주고 그만큼만 탐색을하면 간단히 해결이 된다. pisano값이 150만 이니 모든 계산은 최대 150만 이내로 해결이 될 것이다. 

솔직히.. 피사노 주기를 모른다면 어떻게 풀지..?(물론 푼사람도 있었다... 대단합니다.)