[AC] 9471 피사노 주기

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

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

이건 진짜 피사노주기이다. 바로 전에 풀었던 문제의 원형이라고 볼 수 있다. 우선 이문제에 여러가지 규칙이 있지만 이문제를 풀때는 저 규칙과 전~~~~~혀 상관이 없다. 필자는 저 규칙이 있으니 뭔가 있나? 혹시 DP인가? 싶었지만 아니었다.

피사노주기는 아무리 찾아봐도 외국자료들 뿐이 없었다. 먼저 전에 풀었던 문제는 피사노주기값을 구하기가 굉장히 쉬웠고 그를 통해 값을 구할 수 있었다. 그런데 만약, 정의된 규칙이 통하지 않는 문제라면 어떻게 될까? 

즉 명시된 규칙들

• 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)

이 적용되지 않는 경우라면 어떻게 풀어야 하는가? 정말 난감했다. 위키피디아를 검색해보니 대략 이런 연산이 가능하다고 한다.

피사노 주기

n	1	2	3	4	5	6	7	8	9	10
p	1	3	8	6	20	24	16	12	24	60

출처:https://en.wikipedia.org/wiki/Pisano_period

위의 피사노 주기를 살펴보면 전혀 규칙성이 없다. 그런데 피사노주기 12번째 값을 구하는 예시가 있다. 

12=3*4이다. 여기서 3번재 피사노값과 4번째 피사노값의 최소공배수를 구한다. 그럼 lcm(8, 6)=24가 된다. 실제로 12번째 피사노값은 24이다. 더 응용해보니 12=2*6일때 lcm(3, 24) 이므로 최소공배수는 24이다. 10인 경우는 10=2*5 이므로 lcm(3, 20)=60이 된다. 오!!! 성립하는것 같다!! 하지만...

만약 소수라면? 단적으로 7을 구하는 방법이나, 11을 구하는 방법이 존재하지 않는다. 여기에 다시 위키는 수식을 주었다.

  For prime numbers p, these can be analyzed by using Binet's formula:

 where  is the kth metallic mean

대략 저 수식을 이용하라는것 같은데..k 가 뭐지..? 하며 이것저것 찾아읽었다. 자세한건 직접 저 위의 위키 링크를 가서 숫자이론쪽을 살펴보면 된다. 저기에대략적으로 k값을 정하는 방법 이런게 나오지만, 별의미 없어보이고 너무 어려운 알고리즘은 틀린 알고리즘일 가능성이 농후하다. 

그리고 찾아보니 공통된 알고리즘이 있어 나도 공부해보았다.

        m1 = m2 = 1;
        period = 0;
        do
        {
            int temp = m1;
            m1 = m2;
            m2 = (temp+m2) % m;
            period++;
        } while (!(m1 == 1 && m2 == 1));

살펴보면 m1과 m2가 있는데 이것을 1로 초기화하였다. 피보나치는 2개의 수를 가지고 다음 수를 정하는 것이다. 피보나치의 1번째 2번째는 1이라는 사실을 우리는 알고있다. 

그리고 7번째 줄은 (a + b) mod c = (a mod c + b mod c) mod c

이공식을 이용한 것이라고 한다.  결국 우리는 이전 2개의 수의 합이 현재 피보나치이고 이걸 m으로 나누는 값을 추출하여 주기를 만든다는것을 알고 있으니, 위의 공식을 사용 할 수 있겠다.

여기서 a mod c 는 m1이 되고 b mod c는 m2가 된다. 처음에는 이전 2개의 수를 더하고 m으로 나눈다. 이수는 자동적으로
A mod B가 되기때문에 이제 주기가 계속 나온다. 여기서 다시 처음의 1, 1이 나온다면 주기가 완성이 되었다는 말이니 종료를 하면 되고, 그동안 period가 카운팅되어 이만큼의 주기라는걸 알수있다.

이해하기 힘든 문제였다.

P.S.

이해에 도움을 주신 백준의 두 유저분(cubelover, mendou12)께 감사드립니다.