[백준] 9471번 피사노 주기

출처: [백준] 9471번 피사노 주기

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	853	602	504	75.224%

---

문제

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

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

n	1	2	3	4	5	6	7	8	9	10
F(n)	1	1	2	3	5	8	13	21	34	55
F(n) mod 11	1	1	2	3	5	8	2	10	1	0

나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. 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)을 출력한다.

---

예제 입력 1

5
1 4
2 5
3 11
4 123456
5 987654

예제 출력 1

1 6
2 20
3 10
4 15456
5 332808

---

힌트

• -

---

출처

• 

  ICPC > Regionals > North America > Greater New York Region > 2013 Greater New York Programming Contest D번

  • 문제를 번역한 사람: baekjoon

---

알고리즘 분류

• 수학

---

링크

• ACM-ICPC Live Archive

---

풀이

• 

---

소스코드

import sys

input = sys.stdin.readline

N = int(input())


def fibo(n):
    if len(fibo_list) > n:
        return fibo_list[n]
    else:
        fibo_list[n] = (fibo(n - 1) + fibo(n - 2)) % mod
        return fibo_list[n]


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


for _ in range(N):
    fibo_list = dict()
    fibo_list[0] = 0
    fibo_list[1] = 1
    fibo_list[2] = 1
    idx, mod = map(int, input().split())

    print(idx, cycle())