피사노 주기

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	1367	963	826	73.422%

문제

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이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 P가 주어진다.

각 테스트 케이스는 N과 M으로 이루어져 있다.

N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고 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

출처

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

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 수학
• 정수론

---

처음 문제를 확인하고 증명이 있어 이걸 이용하여 문제의 답을 찾는 것인가 생각했다.

해당 식들을 구현하면서 이건 아닌 것 같다고 생각했고 다른 블로그를 보면서

이러한 문제는 어떤 식으로 접근하는지 확인하였다.

포인트는 피사노 주기는 피보나치수열을 M으로 나눴을 때 이 나머지가 규칙성을 가지고 반복된다는 것

피보나치수열은 F(0) = 0, F(1) = 1 … 나눌 숫자 M >= 2 조건이므로

이후의 연산에서 나머지가 0, 1 순서로 나온다면 주기가 반복된다는 뜻이다.

피보나치수열을 M으로 나누어주고 나머지가 0 과 1이 순서대로 나올 때 까지 반복해주면서

주기를 카운트 하면 문제를 해결 할 수 있다.

참고 : https://en.wikipedia.org/wiki/Pisano_period <- 피사노의 주기 위키

통과된 코드

#include <iostream>
#include <list>

using namespace std;

list<pair<int, int>> tcList;
list<pair<int, int>> resultList;

// 문제의 입력을 처리하는 함수
void GetInput()
{
	int N;
	cin >> N;
	pair<int, int> tempPair;
	while (N-- > 0) {
		cin >> tempPair.first >> tempPair.second;
		tcList.push_back(tempPair);
	}
}

// 피사노의 주기를 확인하는 함수
int PeriodOfPisano(int tc)
{
	int a = 0, b = 1, cnt = 0, temp =0;

	// 주기가 나올때까지 반복해준다.
	while (true)
	{
		// 모듈러 산술 분배법칙
		temp = ((a % tc) + (b % tc)) % tc;
		a = b;
		b = temp;
		cnt++; // 주기가 얼마인지 체크

		// 나머지로 나눈 값이 처음과 같은 0과 1의 순서로 나온다면, 다시 주기가 반복된다는 뜻
		// (F2 = F1 + F0 , 나머지도 계속 반복을 하게 된다.)
		if (a == 0 && b == 1) break; 
	}

	return cnt; // 주기 리턴
}

int main()
{
	GetInput(); // 입력 받기
	
	// 테스트 케이스만큼 순회 
	for (auto iter = tcList.begin(); iter != tcList.end(); iter++) { // 결과값 출력
		cout << iter->first << " " << PeriodOfPisano(iter->second) << "\n"; 
	}

	return 0;
}