pisano period

피보나치 수열을 M으로 나누었을 때, M으로 나눈 나머지가 일정한 주기를 이룬다는 것을 증명했다고 한다. 여기에는 여러가지 있는데, m > 2인 경우에 k(m)은 짝수이다. 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다. k(m) ≤ m2 - 1 k(2^n) = 3×2(n-1) k(5^n) = 4×5n k(2×5^n) = 6n n > 2라면, k(10^n) = 15×10(n-1) 이는 아래 링크에서 자세히 볼 수 있다. https://www.acmicpc.net/problem/9471 이를 이용해 N번째 피보나치 수열을 계산할 수가 있는데, N번째 피보나치 수열의 주기를 구해주고 이를 P라고 하면, dp[N] == dp[N%P]와 같으므로 N%P번째 피보나치 수열의 값을 구..