피보나치 수의 주기 - 피사노 주기

피사노 주기 : 피보나치 수를 MOD (>1) 로 나누면, 특정 주기가 나타난다.

이 주기의 길이를 구하고자 하는데, 일부 특수 case에 대해선 식이 정립되어 있다. (2, 5, 10의 거듭제곱~)

 

나머지는 일일히 노가다로 구해야..

→ fib(0) = 0, fib(1) = 1 이므로, 0과 1이 다시 나타나는 지점이 새로운 cycle 시작 지점.

 

Q, 근데 사이클 중간에 0, 1이 나타날 수 있지 않을까?

→ 피사노 주기를 관찰한 결과, 0 1 세트는 사이클의 시작점에서만 나타남.

수학적인 증명은 잘 모르겠음. Empirical result일 뿐

(+ 0이 나타나기 바로 직전에 항상 MOD-1과 1이 나타난다는 사실도)

 

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

9471번: 피사노 주기

 

이 피사노 주기를 이용해서 엄청나게 큰 N의 피보나치 수를 구할 수 있다.

수가 엄청 크기에, MOD로 나눈 나머지를 요구할 것이므로 주기를 이루니까.

 

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

2749번: 피보나치 수 3