[C++] 백준 9471: 피사노 주기

문제

[C++] 백준 9471: 피사노 주기 SILVER 4
https://www.acmicpc.net/problem/9471

 

---

 

접근 방법

백준 9471번은 피사노 주기(Pisano Period) 를 구하는 문제다.

피보나치 수열을 어떤 정수 m으로 나눈 나머지를 계속 계산하면 수열이 일정한 주기를 가지고 반복된다.
이 반복되는 길이를 피사노 주기라고 한다.

 

예를 들어, 피보나치 수열을 3으로 나눈 나머지를 보면

1 1 2 0 2 2 1 0 1 1 ...

이렇게 특정 구간 이후부터 동일한 패턴이 반복된다.
이 반복되는 길이가 바로 피사노 주기 k(m) 이다.

 

상세 아이디

피사노 주기는 다음 성질을 가진다.

k(m) ≤ m² − 1

 

즉, 최대 m^2번 정도만 확인하면 반드시 주기가 발견된다.
그래서 반복문을 m * m 범위까지만 돌려서 주기를 찾는다.

 

피보나치 수열을 계속 계산하면서 나머지 값만 유지하면 된다.

LL previous = 1, current = 1;

초기 피보나치 값은 F1 = 1, F2 = 1 이다.

 

이후 다음 값은 아래로 계산한다.

k = (previous + current) % m;

 

그런 후, 아래와 같이 갱신하면서 계속 진행한다.

previous = current
current = k

 

주기 판별:

피사노 주기는 1, 1이 다시 등장하는 순간 시작된다.

따라서 다음 조건을 확인하면 된다.

if (previous == 1 && current == 1)
    return i + 1;

이 순간이 주기의 길이가 된다.

 

구현 시 주의할 점

• 피보나치 값을 그대로 계산하면 안 된다
  • 피보나치 수는 매우 빠르게 커지기 때문에 값 자체를 저장하면 오버플로우가 발생한다.
• 데이터 타입은 long long으로 해주어야 정상적으로 출력된다.
  • 처음에 그냥 int로 했다가 테스트 케이스 4번이 0으로 출력되는 현상이 발생했다.

 

---

 

코드

#include <iostream>
using namespace std;

typedef long long LL;

LL pisano(LL m)
{
	LL previous = 1, current = 1;
	LL k = 0;
	for (LL i = 0; i < m * m; i++)  // k(m) <= m^2 - 1
	{
		k = (previous + current) % m;
		previous = current;
		current = k;

		if (previous == 1 && current == 1)
			return i + 1;
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int p = 0;
	cin >> p;

	for (int i = 0; i < p; i++)
	{
		LL n = 0, m = 0;
		cin >> n >> m;

		cout << n << ' ' << pisano(m) << '\n';
	}
}