[Google CodeJam 2008 Round 1A-C][BOJ 12727, 12728, 12925] n 제곱 계산

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

12728번: n제곱 계산

이 문제는 $(3 + \sqrt{5})^n$의 정수부중 마지막 세자리 (혹은 정수부를 1000으로 나눈 나머지라고 생각해도 되겠다)를 구하는 문제인데 $n$번 곱하는 것은 $O(\log{n})$ 번만에 해결이 가능했지만,  $(3 + \sqrt{5})^n = a + b\sqrt{5}$ 라고 할 때 ($a, b$는 정수) $b\sqrt{5}$를 1000으로 나눈 나머지를 구하는 과정에서 부동 소숫점 에러때문에 9년전에 못풀었다가 최근에 다시 풀게된 문제이다.

 

이 문제의 핵심은 크게 두가지로 나뉜다.

 

정리 1) $A_n = (3 + \sqrt{5})^n$ 와 그 켤레 무리수 $B_n = (3 - \sqrt{5})^n$ 를 합치면 정수가 된다.

 

증명) $A_n$ 과 $B_n$을 이항정리를 통해 전개해보면

$A_n = \sum_{k=0}^{\lfloor\frac{k}{2}\rfloor}{{n \choose 2k} 3^{n-2k} (\sqrt{5})^{2k}} + \sum_{k=0}^{\lfloor\frac{k}{2}\rfloor}{{n \choose 2k+1}3^{n-2k-1}(\sqrt{5})^{2k+1}}$

$B_n = \sum_{k=0}^{\lfloor\frac{k}{2}\rfloor}{{n \choose 2k} 3^{n-2k} (\sqrt{5})^{2k}} + \sum_{k=0}^{\lfloor\frac{k}{2}\rfloor}{{n \choose 2k+1}3^{n-2k-1}(-\sqrt{5})^{2k+1}}$

(이항정리로 전개했을 때 짝수 인덱스는 정수가 되고 홀수 인덱스는 무리수가 된다는 사실을 이용해 정수부 + 무리수부 로 분해한 모습이다)

 

전개식을 봤을 때 $A_n$ 의 무리수부와 $B_n$의 무리수부는 서로 역수관계에 있기 때문에 더할 경우 0 이 되고, 실수부는 같으므로 더했을 때 2 배가 된다.

 

따라서 $A_n + B_n = 2 \sum_{k = 0}^{\lfloor k/2 \rfloor}{\binom{n}{2k} 3^{n-2k} (\sqrt{5})^{2k}} = 2 \sum_{k = 0}^{\lfloor k/2 \rfloor}{\binom{n}{2k} 3^{n-2k} 5^{k}}$, 즉 정수이다.

 

정리 2) 켤레 무리수 $(3 - \sqrt{5})^n$ 은 0보다 크고 1보다 작은 실수이다.

 

증명) $3-\sqrt{5}$ 은 $\sqrt{5} \approx 2.236$ 이기 때문에 0보다 크고 1보다 작은 실수이다.

 

그리고 0보다 크고 1보다 작은 실수를 계속 곱하면 원래의 수보다 작아지므로 (하지만 0이 되진 않는다) $0 < (3-\sqrt{5})^{n} < (3-\sqrt{5}) < 1$ 이다.

 

즉 위 두 정리로 부터 알 수 있는 사실은 $C_n = A_n + B_n$ 은 정수이며, 이 수는 $A_n$ 의 정수부보다 1 더 크다 (왜냐하면 $B_n$ 은 0보다 크고 1보다 작은 실수이기 때문에 $C_n > A_n$이지만 $C_{n} \leq \lfloor A_{n} \rfloor + 1$ 이다).

 

따라서, $A_n$ 을 계산해서 부동소숫점 에러를 신경 쓸 필요 없이 $C_n$을 계산한 뒤 그냥 1을 빼버리면 된다!!

 

그럼 이제 $C_n$을 계산하는 방법을 알아보자.

 

$A_n = a + b\sqrt{5}$ 라고 가정하면 ($a, b$는 정수), $B_n = a - b\sqrt{5}$ 이다 ($A_n$의 켤레무리수이므로).

 

그러면, $C_n = A_n + B_n = a + b\sqrt{5} + a - b\sqrt{5} = 2a$ 이다. 

 

즉 $A_n$의 정수부만 구한다음에 2를 곱하면 된다.

 

그럼 $A_n$의 정수부는 어떻게 구할까?

 

$A_{n-1} = a_{n-1} + b_{n-1}\sqrt{5}$이라고 가정하자.

 

그러면

 

$A_n = A_{n-1}(3 + \sqrt{5}) = (a_{n-1} + b_{n-1}\sqrt{5})(3 + \sqrt{5})$

$= (3a_{n-1} + 5b_{n-1}) + (a_{n-1} + 3b_{n-1})\sqrt{5}$ 이다.

 

위 점화식을 이용하여 $O(n)$번만에 구할 수 있다.

 

하지만 $n$의 범위가 20억이하 이므로 위 방법은 시간초과가 날 것이다. 다행히도 우리는 위 식을 다음과 같은 2 x 2 행렬곱으로 나타낼 수 있고 2 x 2 행렬을 n번 곱하는 $O(\log{n})$ 알고리즘이 존재한다.

 

우선 위 식을 어떻게 2 x 2 행렬곱으로 나타낼 수 있는지 살펴보도록 하자.

 

위에 구한 점화식을 이용하면

$a_{n} = 3a_{n-1} + 5b_{n-1}$,

$b_{n} = a_{n-1} + 3b_{n-1}$ 이다.

 

이를 행렬식으로 나타내면

 

$\begin{bmatrix}a_n \\ b_n \end{bmatrix} = \begin{bmatrix} 3 & 5 \\ 1 & 3\end{bmatrix}\begin{bmatrix}a_{n-1}\\b_{n-1}\end{bmatrix}$이다.

 

이는 아래와 같이 나타낼 수 있다.

 

$\begin{bmatrix}a_n \\ b_n \end{bmatrix} = \begin{bmatrix} 3 & 5 \\ 1 & 3 \end{bmatrix}^{n-1} \begin{bmatrix}a_{1}\\b_{1}\end{bmatrix}$ 이다.

 

1) 즉 행렬 $\begin{bmatrix} 3 & 5 \\ 1 & 3 \end{bmatrix}^{n-1}$을 $O(\log{n})$번만에 구한 다음

 

2) $\begin{bmatrix}3\\1\end{bmatrix}$과 곱해서 $a_n$을 구하고

 

3) $a_n$에 2를 곱해서 $C_n$을 구한 뒤

 

4) $C_n$에서 1을 빼서 $A_n$의 정수부를 구하면 된다.

 

2 x 2 행렬을 $O(\log{n})$번만에 구하는 방법은 이 포스트 (작성 예정)를 참고하길 바란다.

 

마지막으로 내가 제출에 사용한 코드를 아래 남긴다.

 

#include <iostream>
#define MOD 1000
using namespace std;
struct matrix {
    int a, b, c, d;
    matrix(int a, int b, int c, int d) 
    	: a(a % MOD), b(b % MOD), c(c % MOD), d(d % MOD) {}
    matrix operator*(const matrix &mat) {
        // 행렬곱 정의
        int a2 = (a * mat.a) % MOD + (b * mat.c) % MOD;
        int b2 = (a * mat.b) % MOD + (b * mat.d) % MOD;
        int c2 = (c * mat.a) % MOD + (d * mat.c) % MOD;
        int d2 = (c * mat.b) % MOD + (d * mat.d) % MOD;
        a2 %= MOD;
        b2 %= MOD;
        c2 %= MOD;
        d2 %= MOD;
        return matrix(a2, b2, c2, d2);
    }
    static matrix pow(const int &n) {
        // 행렬의 n승을 구한다.
        matrix unit = matrix(3, 5, 1, 3);
        matrix ans = matrix(1, 0, 0, 1);
        int n2 = n;
        while (n2) {
            int bit = n2 & 1;
            if (bit) {
                ans = ans * unit;
            }
            unit = unit * unit;
            n2 >>= 1;
        }
        return ans;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N;
        cin >> N;
        matrix mat = matrix::pow(N-1);
        int ans = 2 * (mat.a * 3 + mat.b) - 1;
        // -1 이 될 경우 정수부 마지막이 999 이다.
        if (ans == -1) {
            ans = 999;
        }
        ans %= MOD;
        printf("Case #%d: %03d\n", t, ans);
    }
}