BOJ 12728 n제곱 계산 / 12925 Numbers

난이도 : Solved ac 기준 다이아 5 (개인적으로는 플 1 정도라고 생각한다.)

출처 : Google Code Jam 2008 Round 1A, C번

 

두 문제는 완전히 같은 문제로, 잘 모르지만 과거 번역 과정에서 문제가 중복된 것 같은데 어째서인지 사라지지 않았다. 세부 조건 등에서도 아무런 차이가 없다. 이 문제에서 제한이 작은 small 버전은 BOJ 12727번이다.

 

1. 문제 설명

$(3 + \sqrt{5})^n$ 의 소수점 앞 세 자리를 계산해야 한다.

예를 들어, $(3 + \sqrt{5})^10$ 의 값은 대략 $15490047.9323...$ 이므로 047을 출력하면 된다.  

$n$이 작을 때는 직접 계산할 수 있지만, 수십억 정도의 $n$에 대한 답을 빠르고 정확하게 제시해야 한다. $n$ 이 20억일 때 $(3 + \sqrt{5})$ 의 20억 제곱을 구하는 것은 Python으로도 어림도 없기 때문에, 다른 방법을 찾을 필요가 있다.

 

 

2. 풀이

고등학교 수학...에서라기보다는, 실력정석 같은 책에 가끔 나오는 트릭으로 $3+\sqrt{5}$ 같은 수들을 다룰 때에는$3-\sqrt{5}$ 를 같이 생각하면 도움이 된다. 먼저, $a = 3+\sqrt{5}, b = 3 - \sqrt{5}$ 라고 놓고, 우리가 원하는 답은 $a^n$ 임을 기억하자.

 

이때, $a^n$ 을 구하기는 어렵지만, $a^n + b^n$ 에 대해서는 생각해볼 만한 여지가 많이 있다. $a + b = 6, ab = 4$ 라는 사실을 먼저 파악하고 나면, '이차방정식의 근과 계수와의 관계' 를 적용해 볼 수 있다. $a$ 와 $b$ 가 이차방정식 $x^2 - 6x + 4 = 0$ 의 두 근임을 관찰하자.

 

이제 $a^2 = 6a - 4$, $b^2 = 6b - 4$ 이므로, $a^n = 6a^{n-1} - 4a^{n-2}$ 이고, $b^n = 6b^{n-1} - 6b^{n-2}$ 이다. 특히 $a^n + b^n = c_n$ 이라는 새로운 수열 $c_n$ 을 정의하면, $c_n = 6c_{n-1} - 4c_{n-2}$ 라는, 상당히 계산하기 편한 식이 도출된다.

 

$c_1 = 6, c_2 = 28$ 로 시작하므로, $c_n$ 은 항상 정수이다. 또한, $b^n$ 이 임의의 자연수 $n$에 대하여 1보다 작으므로 $a^n$ 의 정수부분은 $c_n - 1$ 이 되어, $c_n \mod 1000$ 을 빠르게 구할 수 있다면 $a^n$ 의 정수부분 끝 3자리를 쉽게 구할 수 있다.

 

이제부터는 다양한 방법이 있는데, 정해로는 $c_n = 6c_{n-1} - 4c_{n-2}$ 라는 식을 이용해서, 피보나치 수열을 빠르게 계산할 때처럼 $\log n$ 시간에 행렬을 거듭제곱하는 방법이다. $c_n$ 을 어떤 행렬 $P$에 대해 $P^n$ 과 $c_1, c_2$ 에 대한 식으로 쓸 수 있고, 이를 빠르게 계산 (행렬의 크기 $m$ 과 제곱할 지수 $n$ 에 대해 $m^3 \log n$ 시간) 할 수 있으므로, 쿼리를 빠르게 처리할 수 있다.

 

조금 더 쉬운 방법으로는, $6c_{n-1} - 4c_{n-2}$ 라는 식이 직전 두 항에만 의존한다는 사실을 관찰하는 방법이 있다. $c_n$ 으로 가능한 숫자는 1000개이고, $c_a = c_b, c_{a+1} = c_{b+1}$ 이면 $c_{a+k} = c_{b+k}$ 임이 보장되므로 (직전 두 항에 의해서만 정해지므로, $c_{a+2}$ 가 $c_{b+2}$ 와 같고, $\dots$) 연속한 두 항들을 합쳐서 생각하면 많아야 100만 가지 가능한 경우가 있다. 비둘기집의 원리에 의해 100만 번째 항까지 직접 계산해 보면 반드시 Cycle이 존재하며, 이 Cycle을 찾아서 새로 들어오는 숫자를 모듈러로 처리해서 넘겨주는 방법이 있다.

 

 

3. 코드

#include <bits/stdc++.h>
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll

int firstvals[1010100];
int cycle, stp;
int32_t main()
{
    firstvals[1] = 6;
    firstvals[2] = 28;
    for (int i = 3; i<=1005000; i++)
    {
        firstvals[i] = (firstvals[i-1]*6 - firstvals[i-2]*4)+10000;
        firstvals[i] %= 1000;
    }
    int t; scanf("%lld",&t);
    int ct = 0;
    while(t--)
    {
        ct++;
        int x; scanf("%lld",&x);
        int aa;
        if (x > 104) aa = firstvals[(x-4)%100+4];
        else aa = firstvals[x];
        printf("Case #%lld: %03lld\n",ct,(aa+999)%1000);
    }
}

코드가 매우 짧은 이유는, 104 나 4 같은 값들이 앞서 설명한 두 번째 방법 (Cycle 찾기) 을 따로 코딩해서 돌려보고 얻은 결과만 넣었기 때문이다. 가끔 나오는, 실제 제출하는 코드보다 더 많은 코드를 작성해야 하는 유형? 이라고도 할 수 있을듯.