[백준/C++] 9471번: 피사노 주기

문제

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

---

문제 요약

피보나치 수열을 m으로 나눈 나머지로 이루어진 수열은 주기가 존재한다.

 

반복하는 부분 수열의 길이인  k(m)을 출력한다. 

---

코드

#include <iostream>

# define ll long long

using namespace std;

int p;

int main() {
    cin >> p;

    while (p--) {
        ll n, m;
        cin >> n >> m;

        int first = 1;
        int second = 1;
        int tmp;

        for (int i = 2; i < m * m; i++) {
            tmp = first;
            first = second;
            second += tmp;

            first %= m;
            second %= m;

            if (first == 0 && second == 1) {
                cout << n << " " << i << "\n";
                break;
            }
        }

    }
    
    return 0;
}

---

코드 설명

m을 2, 3, 4, 5로 늘려가면서 피사노 수열을 써보면 규칙을 찾을 수 있다.

 

=> 피사노 수열의 N번째 항이 0이고, N + 1번째 항이 1이 될 때의 N이 피사노 주기가 된다.

---

고찰

귀찮아 하지 말고, 직접 손으로 문제를 풀어보는 연습을 하자!!!