baekjoon #9471

 

 

 

 

문제

 

 

 

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

9471번: 피사노 주기

피보나치 수열을 어떠한 수로 나눈 나머지가 주기를 이룬다는 것이 피사노 주기이다.

이 문제는 주기를 구하는 문제인데 https://www.acmicpc.net/problem/2749 피보나치 3을 푸는데 도움을 줄 것이다.

 

 

 

해결

 

 

 

잊지 말아야 한다. 피사노 주기는! 피보나치 수열을 어떠한 수로 나눈 나머지가 주기를 이루는 것이다.

지금까지 작성한 피보나치 관련 포스트들은 배열을 이용했지만 이번에는 반복문을 이용할 것이다.(피보나치 수열의 값들을 모두 기억 하느냐 마느냐의 차이이지 bottom-up 방식이 아닌 것은 아니다.)

이 문제를 해결한 주요한 생각들

1. 피보나치 수열의 0번째 값은 0이고 첫번째 값은 1.

2. F(n) = F(n - 1) + F(n - 2) -- 기본 피보나치 식.

 

나누는 수의 최솟값이 2 인데 0번째 값은 0이고 첫번째 값은 1이라는 사실은 변하지 않는다.(0을 2로 나눈 나머지는 0, 1을 2로 나눈 나머지는 1)

 

그러므로 주기는 어떠한 피보나치 수열 값을 어떠한 수 M으로 나눈 나머지가 0이고 그 다음 피보나치 수열 값을 M으로 나눈 나머지가 1이라면 그것이 '주기' 일 것이다.

 

 

 

소스코드

 

 

 

#include<cstdio>
using namespace std;

void pisano_period(int P);

int main() {
	int P; scanf("%d", &P);
	pisano_period(P);
	return 0;
}

void pisano_period(int P) {
	int N, M;
	long long period;
	int now, pre;
	int temp;
	while (P--) {
		scanf("%d %d", &N, &M);
		now = 1, pre = 1;
		period = 2;
		do {
			temp = now;
			now = (now + pre) % M;
			pre = temp;
			period++;
		} while (!(now == 0 && pre == 1));
		printf("%d %lld\n", N, period);
	}
}