백준[9471] - 피사노 주기

문제

백준 9471 문제 보기

접근 방법

피보나치 수열을 특정 값으로 나눈 나머지가 주기를 이룬다는 피사노 주기를 구현하는 문제이다. 배열을 사용하면 간단하게 풀수 있지만 데이터의 범위가 너무 많아 배열은 사용할 수 없다.
새롭게 생각한 방법은 피보나치 수열을 계속 구하되 n-2와 n-1이 수열의 시작인 0과 1일 경우 주기가 시작되는 위치라는 점을 활용했다.

코드

#include <iostream>

using namespace std;

int T, m, m1, m2, cnt;

int main() {
    int n;
    cin >> n;

    while (n--) {
        cin >> T >> m;

        m1 = 0;
        m2 = 1;
        cnt = 0;

        while(1) {
            if(m1 == 0 && m2 == 1 && cnt != 0) {
                break;
            }
            int temp = m1;
            m1 = m2;
            m2 = (temp + m1) % m;
            cnt ++;
        }

        cout << T << ' ' << cnt << endl;
    }
    return 0;
}