피사노 주기

문제

1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다.

예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다.

나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10임을 알 수 있다. Wall은 아래와 같은 여러 가지 성질도 증명했다.

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

m이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000)

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고 k(M)을 출력한다.

예제 입력

5
1 4
2 5
3 11
4 123456
5 987654

예제 출력

1 6
2 20
3 10
4 15456
5 332808

분할 정복 단계의 피보나치 수 3 #2749번을 푸는데 막혀서 고민하다가 피사노 주기가 사용된다는것을 알고 이 문제부터 풀어보기 시작했다. 문제에서 볼 수 있듯이 피보나치 수열 각 항을 m으로 나눠가다 보면 1 과 0이 연속으로 나오는 경우가 반드시 존재하고, 이 다음부터는 1+0 = 1, 0+1 =1로 피보나치 수열 나머지들의 다음 주기가 시작된다.

피보나치 수열을 m으로 나눈 나머지를 fibo라는 dictionary에 저장하고, cycle함수를 통해 1,0이 처음으로 연속해서 나타나는 구간을 탐색했다.

• 이 문제도 메모이제이션을 활용했다. DP

Code

def pisano(x):
    if len(fibo) > x:
        return fibo[x]
    else:
        fibo[x] = (pisano(x-1)+pisano(x-2)) % m
        return fibo[x]


def cycle():
    x = 1
    while True:
        if fibo[x] == 0 and fibo[x-1] == 1:
            return x
        x += 1
        pisano(x)


for _ in range(int(input())):
    fibo = dict()
    fibo[0] = 0
    fibo[1] = 1
    fibo[2] = 1
    a, m = map(int, sys.stdin.readline().split())

    print(a, cycle())

#2749 피보나치 수 3에서는 이를 활용해 문제를 풀어야한다. 첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력하라고 했으니, 피사노 주기를 구한다면 시간초과 없이 효율적으로 풀 수 있을 것이다.

함수를 돌려보면 1,000,000의 피사노 주기는 1,500,000이란걸 알 수 있다.

이를 활용해 피보나치 수 3 문제를 풀어보자.

[다시 풀어보기] ✔ - 2020.10.26