BOJ 9471 피사노 주기

피보나치 수를 m으로 나눈 수들을 순서대로 나열하면 일정 주기로 반복이 된다고 한다.
그 주기를 피사노 주기(Pisano period)라고 하는데, 피보나치 수열을 구성하는 피보나 치 수들을 각각 어떤 수 m으로 나눠서 그 나머지들로 수열을 만들 때, 반복되는 부분 수열의 길이를 구하는 문제이다.

문제에 보면

• m > 2인 경우에 k(m)은 짝수이다.
• 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
• k(m) ≤ m2 - 1
• k(2n) = 3×2(n-1)
• k(5n) = 4×5n
• k(2×5n) = 6n
• n > 2라면, k(10n) = 15×10(n-1)

(출처 : https://www.acmicpc.net/problem/9471)

이렇게 성질도 주어지는데,  m이 (2의 n제곱)이거나 (5의 n제곱)이거나 2*(5의 n제곱)이거나, (n>2인 10의 n제곱)이라면 바로 수식으로 피사노 주기를 구할 수 있지만, 이 외의 경우에 해당하는 m이 주어지면 어떻게 해야할까?
바로 질문 검색의 질문과 답변과 어느 분의 블로그를 참고했다.

핵심은
(a + b) mod c = (a mod c + b mod c) mod c 
피보나치 수열에서 한 수는 그 수 바로 이전의 두 수의 합으로 결정된다는 것!

일단 m으로 나눈 나머지의 주기를 구해야 하는데 어디까지가 주기일까? 피보나치 수열을 구성하는 피보나치 수는 그 수 바로 이전의 두 피보나치 수의 합으로 결정되어 나가므로 두 개의 수가 같다면 즉 문제에서 주어진 피보나치 수는 1, 1 부터 시작하므로(m으로 나눈 나머지 역시 1, 1) 1, 1, 이 나올 때부터 또 다른 주기가 시작된다고 볼 수 있다!
근데 mod m을 한 값들인데 두 개의 수가 같다고 거기서부터 또 똑같이 반복된다고 볼 수 있을까? 정말 원래 피보나치 수열을 나눈 값으로 계산해도 그렇게 나올까?

피보나치 수 X, Y, Z가 있다고 하자. Z = X+Y일 것이다.
Z mod M = (X+Y) mod M
             = (X mod m + Y mod M) mod M
지금 우리가 구하는 것은 피보나치 수를 M으로 나눈 나머지들로 이루어진 수열의 주기를 구하는 것인데, 이렇게 피보나치 수 Z를 M으로 나눈 나머지는 Z를 구성하는 X+Y에서 X를 M으로 나눈 나머지와 Y를 나눈 나머지의 합을 M으로 나눈 것과 같은 것을 볼 수 있다.

즉, 직접 피보나치 수열을 계산해서 M으로 나눈 나머지를 구하는 것이나 처음부터 피보나치 수의 나머지들로 더하고 나눈 나머지를 구하는 것이나 같다는 것이므로 제대로 된 값이 나올까하는 걱정은 안 해도 된다.

그래서 이렇게 나머지들로 이루어진 수열도 1, 1, 로 시작해서 더하고 나누는 식으로 해서 계속 수열을 구해 나가다가 1, 1,을 만나면 거기서부터 또 다른 주기가 반복된다는 것을 알 수 있다.

이렇게 피보나치 수열은 앞의 두 값에 의해 하나 하나 결정되어 나가고, 위의 나머지 연산 법칙에 의하면 피보나치 수를 나눈 나머지 값을 이용해 수열을 만들어도 피보나치 수를 구해서 나눈 나머지와 같으므로, 피보나치 수를 나눈 나머지 값들로 구성된 수열을 만들어 가면서 연속된 두 값만 확인하면 주기를 쉽게 찾을 수 있는데, 나는 그냥 모든 수를 다 비교할 생각을 했으니... 음 정말 좋은 문제이다.

< 참고 및 출처 >
 https://www.acmicpc.net/board/view/4501
 http://redsalmon.tistory.com/5