백준 9471번 C++ 풀이

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

9471번: 피사노 주기

 

 

피보나치 수열을 자연수 K로 나눈 나머지를 수열로 볼 때, 이 수열에 주기성이 생긴다, 이때의 주기를 피사노 주기라고 한다. 

 

편의를 위해 피보나치 수열을 K로 나눈 나머지로 이루어진 수열을 피사노 수열이라고 하겠다.

 

이 문제는 규칙성을 찾아야 한다. 피사노 주기의 성질을 다 무시하고 K를 2, 3, 4, 5, .......로 늘려가면서 피사노 수열을 써보면 규칙이 보이게 되는데, 피사노 수열의 N번째 항이 0이고 N+1번째 항이 1이 될 때의 N이 피사노 주기가 된다.

 

이걸 파악한 순간 문제는 푼 것과 다름없다.

 

#include <iostream>

using namespace std;

typedef long long ll;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test; // 전체 테스트케이스 개수
    int testCase; // 케이스 번호
    ll n; // input
    ll i; // 반복인자
    int first = 1, second = 1; // 나머지를 저장할 두 변수
    int temp; // 임시 저장
    cin >> test;

    while (test--) {
        first = 1; second = 1;
        cin >> testCase >> n;
        for(i = 2; i < n * n - 1; i++) { // 수열 전체를 저장하지 않고 0과 1이 나오는 부분만 찾는다.
            temp = first;
            first = second;
            second += temp;
            first %= n; second %= n;
            if (first == 0 && second == 1) break;
        }
        cout << testCase << ' ' << i << '\n';
    }
}