[c++] 백준 9471 - 피사노 주기(피사노 주기, 반복 찾기)

0. 주어진 문제

피사노 주기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	398	284	233	78.716%

문제

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) ≤ m² - 1
• k(2ⁿ) = 3×2^(n-1)
• k(5ⁿ) = 4×5ⁿ
• k(2×5ⁿ) = 6n
• n > 2라면, k(10ⁿ) = 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

1. 풀이

어우, 피보나치 수열 3번 문제를 푸는데, 전혀 풀 방법이 나오질 않아서 찾다가 이 문제를 우선 풀게 되었다.

우선, 피사노 주기란 피보나치 수열 F 가 주어졌을때, 그 수열을 N으로 나눴을 때 이 나머지가 규칙성을 가지고 반복된다는 것이다.

피보나치 수열이 자기를 계속 더하는 수열이다보니 이러한 성질을 띄게 된 것 같은데, 하여튼, 이 주기를 찾기 위해서 F0=0, F1=1이고, 나머지로 나눈 값도 0과 1이다.

 즉, 나머지로 나눈 값이 0과 1의 순서로 나온다면, 다시 주기가 반복된다는 뜻이다.(F2 = F1 + F1 이므로, 나머지도 계속 반복을 하게 된다.)

 근데, 여기서 좀 궁금한 것은, 반복이 0, 1 순서가 아닌 갑자기 이상한 수들이 반복되는 경우는 전혀 없나?

 궁금한데, 내가 답을 구해낼 수는 없을 것 같네 ㅋㅋㅋㅋ 언젠가 알게되면 다시 쓰자.

1) 피보나치 수열을 만들면서, 그 값을 입력한 M으로 나누며 나머지가 반복되는지 계속 확인한다.

2) 그 계산을 하면서, 한편으로는 수열의 길이를 따로 카운트한다.

3) 반복이 시작되면, 지금까지의 길이를 반환하면 끝난다.

뭐, 추가적으로

π(n)	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	+11	+12
0+	1	3	8	6	20	24	16	12	24	60	10	24
12+	28	48	40	24	36	24	18	60	16	30	48	24
24+	100	84	72	48	14	120	30	48	40	36	80	24
36+	76	18	56	60	40	48	88	30	120	48	32	24
48+	112	300	72	84	108	72	20	48	72	42	58	120
60+	60	30	48	96	140	120	136	36	48	240	70	24
72+	148	228	200	18	80	168	78	120	216	120	168	48
84+	180	264	56	60	44	120	112	48	120	96	180	48
96+	196	336	120	300	50	72	208	84	80	108	72	72
108+	108	60	152	48	76	72	240	42	168	174	144	120
120+	110	60	40	30	500	48	256	192	88	420	130	120
132+	144	408	360	36	276	48	46	240	32	210	140	24

이게 1부터 144까지 피사노 주기의 크기고,

k	F (k)	π(F (k))	first half of cycle (for even k ≥ 4) or first quarter of cycle (for odd k ≥ 4) or all cycle (for k ≤ 3) (with selected second halves or second quarters)
1	1	1	0
2	1	1	0
3	2	3	0, 1, 1
4	3	8	0, 1, 1, 2, (0, 2, 2, 1)
5	5	20	0, 1, 1, 2, 3, (0, 3, 3, 1, 4)
6	8	12	0, 1, 1, 2, 3, 5, (0, 5, 5, 2, 7, 1)
7	13	28	0, 1, 1, 2, 3, 5, 8, (0, 8, 8, 3, 11, 1, 12)
8	21	16	0, 1, 1, 2, 3, 5, 8, 13, (0, 13, 13, 5, 18, 2, 20, 1)
9	34	36	0, 1, 1, 2, 3, 5, 8, 13, 21, (0, 21, 21, 8, 29, 3, 32, 1, 33)
10	55	20	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (0, 34, 34, 13, 47, 5, 52, 2, 54, 1)
11	89	44	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (0, 55, 55, 21, 76, 8, 84, 3, 87, 1, 88)
12	144	24	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (0, 89, 89, 34, 123, 13, 136, 5, 141, 2, 143, 1)
13	233	52	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14	377	28	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15	610	60	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16	987	32	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17	1597	68	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18	2584	36	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19	4181	76	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20	6765	40	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21	10946	84	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22	17711	44	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23	28657	92	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
24	46368	48	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

이건 나머지 값들이 어떻게 되어있는지 나와있다.

또, 나누는 수가 2와 5의 배수인 경우 값이 한정되나 보다

• If n = 2^k, then π(n) = 3·2^k–1 = 3·2^k/2 = 3n/2.
• if n = 5^k, then π(n) = 20·5^k–1 = 20·5^k/5 = 4n.

2. 소스코드

#include<iostream>
 
using namespace std;
 
int fisano_period(int m) {
    int count = 0, m1 = 0, m2 = 1;
    do {
        int temp = m1;
        m1 = m2;
        m2 = (temp + m1) % m;
        count++;
    } while (m1 != 0 || m2 != 1);    //0,1이 나온다는 것은 주기가 반복된다는 것이다.
 
    //지금까지 길이를 반환한다.
    return count;
}
 
 
int main() {
    int P, N, M;
    cin >> P;
    for (int i = 0; i < P; i++) {
        cin >> N >> M;
        cout << N << " " << fisano_period(M) << endl;
    }
}

3. 문제 출처

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

4. 참고

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