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

 

문제

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

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

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

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

m이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000)

출력

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

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N[1001], M[1001];
int P, cnt;
vector<int> v;

void pisano(int n, int m)
{
	v.push_back(0);
	v.push_back(1);
	v.push_back(1);
	cnt = 2;

	while (1)
	{
		v.push_back((v[cnt] + v[cnt - 1]) % m);
		cnt++;

		if(v[cnt] == 0 && v[cnt-1] == 1) break;
	}

	cout << n << " " << cnt << endl;
	
	v.clear();

}

int main()
{
	cin >> P;

	for (int i = 1; i <= P; i++)
	{
		cin >> N[i] >> M[i];
	}

	for (int i = 1; i <= P; i++)
	{
		pisano(N[i], M[i]);
	}

}

 

풀이 방법

피보나치 수열을 구하는 방식으로 수들을 구하는데 m으로 나눠주면서 벡터에 push 하였고
벡터의 맨 마지막 원소가 v[cnt] = 0, 그리고 벡터의 맨 마지막 바로 앞의 원소 v[cnt-1] = 1 일 때,
다시 피보나치 수열이 1부터 시작하므로 주기를 구할 수 있게 됩니다. 

 

 

www.acmicpc.net/problem/9471

9471번: 피사노 주기