피사노 주기

문제

백준 9471번 - 피사노 주기

언어

JavaScript

순서도

피사노 주기의 성질을 이해하고, 피사노 주기 구해서 출력

문제 풀이 step 1

1960 년, IBM 의 직원 Donald Wall 은 피보나치 수열을 m 으로 나눈 나머지가 주기를 이룬다는 것을 증명했다고 합니다.
이외에도 다음과 같은 여러 가지 성질도 증명했다고 합니다.
- k(m) 은 피보나치 수열이 반복되는 부분 수열의 길이라고 합니다.
- m > 2 인 경우, k(m) 은 짝수입니다.
- 임의의 짝수 정수 n > 2 에 대해서, k(m) = n 인 m 이 항상 존재합니다.
- k(m) <= m ^ 2 - 1
- k(2 ^ n) = 3 * 2 ^ (n - 1)
- k(5 ^ n) = 4 * 5 ^ n
- k(2 * 5 ^ n) = 6n
- n > 2 라면, k(10 ^ n) = 15 * 10 ^ (n - 1)
위의 성질 외에도, 가장 중요한 성질은 반복되는 부분 수열의 맨 앞의 값 2 개가 0 과 1 로 이루어져 있다는 사실입니다.
- 즉, 0, 1, x, x, x, x, ... 과 같은 모양으로 반복된다는 것입니다.
피사노 주기에 관해서 더 궁금하시면, https://en.wikipedia.org/wiki/Pisano_period 를 참고하시면 좋을 것 같습니다.

문제 풀이 setp 2

본 문제는 피보나치 수열이 반복되는 부분 수열의 길이를 구하는 문제입니다.
위에서 설명한 가장 중요한 성질을 이용합니다.
주어진 m 으로 나머지 연산을 수행하며 피보나치 수열을 키워가다가 0 과 1 로 시작되는 지점을 찾습니다.
그 지점까지가 부분 수열의 길이이며, 그 값을 출력하면 정답이 됩니다.
추가 설명은 주석으로 작성하겠습니다.

후기

백준 2749번 - 피보나치 수 3 을 풀려다가 안 풀려서 알게된 문제입니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const getPisanoPeriodLength = (MAX, m) => {
	if (m === 1) return 1;

	let [fibonacci_0, fibonacci_1] = [0, 1];

	// 나머지 연산을 수행하면서 피보나치 수열의 값을 키워가다가 0 과 1 로 시작되는 지점 찾기
	for (let i = 1; i < MAX; i++) {
		[fibonacci_0, fibonacci_1] = [fibonacci_1, (fibonacci_0 + fibonacci_1) % m];
		if (fibonacci_0 === 0 && fibonacci_1 === 1) return i;
	}
};

const solution = (input) => {
	const MAX = 1000000;
	const T = Number(input[0]);

	let res = "";
	for (let i = 1; i < 1 + T; i++) {
		const [n, m] = input[i].split(" ").map(Number);
		res += n + " " + getPisanoPeriodLength(MAX, m) + "\n";
	}

	return res;
};

console.log(solution(input));