백준 12925번: Numbers

www.acmicpc.net/problem/12925

12925번: Numbers

---

다소 발상이 힘든 풀이를 가진 문제입니다.

 

우선 문제는 $M\leq \left ( 3+\sqrt{5} \right )^{n}\leq M+1$ 일 때 $M$ 의  $modulo$  1000 값을 구하라는 것입니다.

---

가볍게 $n=1$ 인 상황부터 생각해봅시다.

 

계산기를 써보면 $\left ( 3+\sqrt{5} \right )^{1}=3+\sqrt{5}=5.236067\cdots$ 이므로, 정수부는 5가 됩니다.

 

그런데, 라이브러리의 round함수를 쓰지 않고 이를 어떻게 알 수 있을까요?

 

일단, $3+\sqrt{5}$ 에서 뭔가를 이용해 정수를 뽑아내야하니, 다음과 같이 변형해보겠습니다.

 

$\left ( 3+\sqrt{5} \right )=\left \{ 5+\left ( \sqrt{5}-2 \right ) \right \}$

 

$2\leq \sqrt{5}\leq 3$ 이므로 5가 정수부임을 확인할 수 있게 되었습니다.

 

그런데 위 식에서 얻은 $5$는 다시 이렇게 변형할 수 있습니다.

 

$5=\left \{ \left ( 3+\sqrt{5} \right )+\left ( 3-\sqrt{5} \right ) \right \}-1$

 

이제 이 식을 기억해야 합니다.

 

다시 $n=2$ 인 상황에 대해 같은 과정을 거쳐봅시다.

 

계산기를 써보면 $\left ( 3+\sqrt{5} \right )^{2}=14+6\sqrt{5}=27.416407\cdots$ 정수부 27을 얻습니다.

 

실제로 $14+6\sqrt{5}$ 를 다음과 같이 변형할 수 있습니다.

 

$\left ( 14+6\sqrt{5} \right )=\left \{ 27+\left ( 6\sqrt{5}-13 \right ) \right \}$

 

$\left ( \because 169\leq 180\leq 196\Leftrightarrow 13\leq 6\sqrt{5}\leq 14 \right )$

 

이제 다시 $27$을 변형해보면 다음을 얻습니다.

 

$27=\left \{ \left ( 14+6\sqrt{5} \right )+\left ( 14-6\sqrt{5} \right ) \right \}-1$

 

$\therefore 27=\left \{ \left ( 3+\sqrt{5} \right )^{2}+\left ( 3-\sqrt{5} \right )^{2}\right \}-1$

 

 

이런 상황이 다른 $n$ 의 값에 대해서도 성립함을 보일 수 있을까요?

 

수학적 귀납법을 통해 보이겠습니다.

---

 

우선, 우리는 1차적으로 $\left ( 3+\sqrt{5} \right )^{n}+\left ( 3-\sqrt{5} \right )^{n}$ 의 값이 정수임을 보여야 합니다.

 

뜬금없을 수도 있지만, 다음 2차방정식을 생각해 보겠습니다.

 

$x^{2}-6x+4=0$

 

이 방정식의 근은 $x=3\pm \sqrt{5}$입니다. $\alpha =3+\sqrt{5}$ , $\beta =3-\sqrt{5}$ 라고 해보겠습니다.

 

우리가 원하는 건 $\alpha^{n}+\beta^{n}$ 의 정수 여부가 되겠습니다.

 

이제 위 2차방정식의 양변에 $x^{n}$을 곱하고, 인수분해하겠습니다.

 

그러면 다음을 얻습니다.

 

$x^{n+2}-6x^{n+1}+4x^{n}=x^{n}\left \{ x-\left ( 3+\sqrt{5} \right ) \right \}\left \{ x-\left ( 3-\sqrt{5} \right ) \right \}=0$

 

따라서, 다음 두 식이 성립합니다.

 

$\alpha^{n+2}-6\alpha^{n+1}+4\alpha^{n}=0$

$\beta^{n+2}-6\beta^{n+1}+4\beta^{n}=0$

 

 

그러므로 다음 점화식을 얻을 수 있습니다.

 

$\alpha^{n+2}+\beta^{n+2}=6\left ( \alpha^{n+1}+\beta^{n+1} \right )-4\left ( \alpha^{n}+\beta^{n} \right )$

 

 

이제, $\left ( \alpha^{k}+\beta^{k} \right )$ 와 $\left ( \alpha^{k+1}+\beta^{k+1} \right )$ 이 동시에 정수인 자연수 $k$ 가 존재한다면 $\left ( \alpha^{k+2}+\beta^{k+2} \right )$ 도 정수가 됨을 알 수 있습니다.

 

 

그런데 위에서 우리는 $\left ( \alpha+\beta \right )=6$ , $\left ( \alpha^{2}+\beta^{2} \right )=28$ 임을 밝혔습니다.

 

따라서 위 조건을 만족하는 자연수 $k$가 $k=1$로 존재하여, 수학적 귀납법에 의해

 

$\alpha^{n}+\beta^{n}\in \mathbb{Z}$    (단, $n\in \mathbb{N}$)

 

라는 사실이 증명되었습니다.

---

 

2차적으로 우리는 다음 조건을 만족하는 정수 $M$ 이 항상 존재함을 알 수 있습니다.

 

즉, $\alpha^{n}$ 의 정수부가 이 경우에는 $M$으로서 반드시 존재합니다.

 

$M<\alpha^{n}<M+1$    (단, $n\in \mathbb{N}$)

 

그런데 $0<\beta=3-\sqrt{5}<1$ 이므로,    $0<\beta^{n}<1$ 입니다.

 

따라서, $\alpha^{n}+\beta^{n}\in \mathbb{Z}$ 를 만족하기 위해, 다음이 성립합니다.

 

 

$\alpha^{n}+\beta^{n}=M+1$

 

 

즉, 다음 식이 자연수 $n$에 대해 항상 성립합니다.

 

$M<\alpha^{n}<M+1 \Rightarrow M=\left ( \alpha^{n}+\beta^{n} \right )-1=\left \{ \left ( 3+\sqrt{5} \right )^{n}+\left ( 3-\sqrt{5} \right )^{n} \right \}-1$

---

이제 거의 다 왔습니다.

 

수열 $\left \{ X_{n} \right \}$ 을 다음과 같이 정의하겠습니다.

 

$X_{n}=\alpha^{n}+\beta^{n}$

 

 

앞서 밝혔던 대로, $\left \{ X_{n} \right \}$ 에는 다음과 같은 점화식이 성립합니다.

 

$X_{n+2}=6X_{n+1}-4X_{n}$

 

 

$n$이 충분히 작은 경우 $X_{n}$ 을 구하려면 $O\left ( N \right )$ 으로 충분하지만

 

이 문제에서 $n\leq 10^{9}$ 이므로 보다 빠른 점화식을 구해야합니다.

 

위 점화식을 다음과 같은 행렬로 바꿔줍니다.

 

$\begin{bmatrix}X_{n-1}\\ X_{n}\end{bmatrix}=\begin{bmatrix}0 & 1\\ -4 & 6\end{bmatrix}\begin{bmatrix}X_{n-2}\\ X_{n-1}\end{bmatrix}$  (단, $n>2$)

 

 

이제 이를 활용하게 되면 $O\left ( logN \right )$ 이므로 충분히 빠르게 구할 수 있게 되었습니다.

 

음수 모듈러와 출력 형식에 주의하여 구현하면 해결됩니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>

typedef struct {
	int array[2][2];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, int power);

int main() {
	int T;
	scanf("%d", &T);
	for (int c = 1; c <= T; c++) {
		int N;
		scanf("%d", &N);
		printf("Case #%d: ", c);
		if (N == 2) {
			printf("027\n");
			continue;
		}
		Matrix Base;
		Base.array[0][0] = 0, Base.array[0][1] = 1, Base.array[1][0] = -4, Base.array[1][1] = 6;
		Matrix Answer;
		Answer.array[0][0] = 6, Answer.array[1][0] = 28, Answer.array[0][1] = Answer.array[1][1] = 0;
		Base = matrix_power_modular (Base, N - 2);
		Answer = matrix_multiply_modular (Base, Answer);
		int x = Answer.array[1][0] - 1;
		if (x == 0) {
			printf("000\n");
		}
		else if (x < 10) {
			printf("00%d\n", x);
		}
		else if (x < 100) {
			printf("0%d\n", x);
		}
		else {
			printf("%d\n", x);
		}
	}
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B) {
	Matrix result;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			result.array[i][j] = 0;
			for (int k = 0; k < 2; k++) {
				int temp = (A.array[i][k] * B.array[k][j]) % 1000;
				if (temp < 0) {
					temp += 1000;
				}
				result.array[i][j] = (result.array[i][j] + temp) % 1000;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, int power) {
	Matrix result;
	result.array[0][0] = result.array[1][1] = 1;
	result.array[1][0] = result.array[0][1] = 0;
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular (result, A);
		}
		A = matrix_multiply_modular (A, A);
		power /= 2;
	}
	return result;
}

 

(C11, 1116KB, 0ms, 제출번호 26408276)

---

풀이를 모르겠어서 꽤 헤맸는데, 다음 링크에서 도움을 받을 수 있었습니다.

 

(seokjin2.tistory.com/13)

 

위 링크의 풀이에 조금 더 살을 덧대 보았습니다.