BOJ_9471_피사노 주기 (C++)

[Silver IV] 피사노 주기 - 9471

문제 링크

성능 요약

메모리: 8292 KB, 시간: 4 ms

분류

브루트포스 알고리즘, 수학, 정수론

제출 일자

2024년 12월 6일 16:24:49

문제 설명

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가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고 k(M)을 출력한다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int n, m;
    cin >> n >> m;
    int first = 1;
    int second = 1;
    int third = (first + second) % m;
    bool flag = false;
    vector<pair<int, int>> pisanoPair;
    pisanoPair.push_back({first, second});

    while (!flag) {
        third = (first + second) % m;
        first = second;
        second = third;

        if (first == pisanoPair[0].first && second == pisanoPair[0].second)
            flag = true;

        if (!flag) pisanoPair.push_back({first, second});
    }
    cout << n << " " << pisanoPair.size() << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}