Easy is Perfect

[백준] 9471번 C/C++ 풀이 _ 피사노 주기

  • melonicedlatte
  • Aug 28, 2018


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

피사노 주기

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB28321518681.938%

문제

1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다.

예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다.

n12345678910
F(n)11235813213455
F(n) mod 1111235821010

나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10임을 알 수 있다.

Wall은 아래와 같은 여러가지 성질도 증명했다.

  • m > 2인 경우에 k(m)은 짝수이다.
  • 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
  • k(m) ≤ m2 - 1
  • k(2n) = 3×2(n-1)
  • k(5n) = 4×5n
  • k(2×5n) = 6n
  • n > 2라면, k(10n) = 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

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2013 Greater New York Programming Contest D번

풀이

피보나치 수열에서의 규칙을 찾는 문제입니다.
N 번째에 mod(K) 가 0, N + 1 번째에 mod(K) 가 1 이 나오는 경우에 피사노 주기를 만족하는 N 을 구할 수 있습니다. 

문제에서 주의해야 될 점은 피보나치를 계속해서 갱신할 때, % 연산을 통하여 지속적으로 나머지만 남겨야 된다는 것입니다.
자세한 풀이는 소스코드를 참조해주세요!

https://dongyeollee.github.io/2018/08/09/Al/9471/ 
위와 같은 다른 풀이도 있습니다. 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std; 
 
int main() {
    ios::sync_with_stdio(false); 
    int P;
    cin >> P;
    while (P--) {
        int num, m; 
        cin >> num >> m; 
 
        // 피보나치 만들기
        vector<int> fibonaci;
        fibonaci.push_back(0);    fibonaci.push_back(1);    fibonaci.push_back(1);
 
        // 새로 피보나치를 계속 갱신하면서 나머지를 확인한다
        int n = 3;
        while (1) {
            fibonaci.push_back((fibonaci.at(n - 2) + fibonaci.at(n - 1)) % m);
            if (fibonaci.at(n - 1) % m == 0 && fibonaci.at(n) % m == 1)
                break;
            n++;
        }
        cout << num << " " << n - 1 << "\n";
    }
    return 0;
}
cs



Search