피보나치 수 행렬

11778 피보나치 수와 최대공약수 행렬 계산 방법

누가 포스팅 해놓은 것도 없고, 찾으려고하니 왜 이렇게 생각해야 되는게 많은 건지...일단 메모리 제한이 256MB라 메모이제이션 혹은 DP를 생각했는데 .. 시간초가 런타임 에러 뿜뿜...재귀함수를 만들던,, 메모이제이션을 하던 DP를 하던 O(n) 시간이 걸려서 이건 안되겠다...생각했다. 그래서 검색해보니 피보나치 수열을 계산하는 방법 중에 1. 피사노 주기(Pisano Period)2. 행렬 곱셈들이 있었는데 , 1번은 우리가 계산해야 되는 값이 1,000,000,000,000,000,000 처럼 길고 답을 1,000,000 와 같은 값의 나머지로출력할때 유용하게 쓰인다. 10^k로 나눈 피보나치 수의 나머지들을 반복적인 값의 형태를 띈다. 그것을 피사노 주기! 하지만, 피사노 주기도 O(n)이 ..