Intro
등비수열 $a_{n} = ar^{n-1}$의 합은
$$
S_n = \begin{cases}
an &\text{if } r=1\ \newline
\frac{a(r^n - 1)}{r-1} &\text{otherwise}
\end{cases}
$$
로 나타낼 수 있습니다.
$r=1$일 때 $S_n$이 다른 이유는, $\frac{a(r^n - 1)}{r-1}$의 분모가 $0$이 되기 때문입니다.
이때는, $1$항부터 $n$항까지가 모두 $a$로 같으니, 간단하게 $an$으로 나타낼 수 있습니다.
$n$이 커지면 커질 수록 $S_n$은 (말 그대로) 기하급수적으로 커지기 때문에, 일반적으로 PS에서는 $S_n$을 $m$으로 나눈 나머지를 구하도록 합니다.
따라서, 이 글에서는 등비수열의 합 $S_n\ \textrm{mod}\ m$을 빠르게 구할 방법을 소개하겠습니다.
모듈로 곱셈 역원 ($m$은 소수)
$0$이 아닌 실수 $a$의 곱셈 역원은 $a^{-1}$이라 표기하고, $aa^{-1} = 1$입니다.
비슷하게도, 모듈러 상에서도 곱셈 연산과 역원을 정의할 수 있습니다. 정수 $a$와 소수 $p$에 대하여, $a$와 $p$가 서로소일 때, 법 $p$에 대하여 $a$의 곱셈 역원 $a^{-1}$이 유일하게 존재합니다.
즉, $aa^{-1} \equiv 1\ (\textrm{mod}\ p)$을 만족하는 곱셈 역원 $a^{-1}$가 법 $p$에 대해 유일하게 존재 합니다.
증명은 다음과 같습니다. $ax \equiv 1\ (\textrm{mod}\ p)$를 $ax + py \equiv 1\ (\textrm{mod}\ p)$로 변형합니다. $\gcd(a, p) = 1$이라 가정했으므로, 확장 유클리드 호제법을 이용하여, $ax + py = \gcd(a, p) = 1$을 만족하는 정수 쌍 $(x_0, y_0)$를 구할 수 있고, 모든 정수 $t$에 대해 위 부정방정식의 해는 $(x_0 + tp, y_0 - ta)$꼴입니다. 여기서 $0 \le x_i < p$를 만족하는 $x_i$는 유일하고, 모든 $x_i$는 법 $p$에 대해 서로 합동입니다. 따라서, $x_0\ \textrm{mod}\ p$를 위의 합동식 $ax \equiv 1\ (\textrm{mod}\ p)$에 대입해보면, $x_0\ \textrm{mod}\ p$가 우리가 찾던 $a^{-1}$이라는 사실을 알 수 있습니다.
그렇다면, 실제 $a^{-1}$을 어떻게 구할 수 있을까요? $1$부터 $p - 1$까지의 모든 정수를 $a$에 곱해서 $1$과 법 $p$에 대해 일일히 합동인지 확인해보면 $\mathcal{O}(p)$가 걸려 너무 느립니다.
여기서 페르마의 소정리 $$ a^{p-1} \equiv 1\enspace\ (\textrm{mod}\ p) $$ 를 이용할 수 있습니다.
위 합동식의 양변에 $a^{-1}$을 곱하면, $a^{p-2} \equiv a^{-1}\ (\textrm{mod}\ p)$가 됩니다. 즉, $a^{p-2}\ (\textrm{mod}\ p)$에서 우리가 $a$와 $p$를 모두 알고 있기 때문에 그 값을 직접 계산할 수 있고, 이 값이 곧 $a^{-1}$이 됩니다.
갑작스럽게 등장해서 조금 어려울 수도 있지만, 이런 게 있다는 정도만 알고 넘어갑시다…
따라서, 등비수열의 합 $S_n = \frac{a(r^n - 1)}{r-1}$은 법 $m$에 대해 $S_n \equiv a(r^n -1)(r - 1)^{m - 2}\ (\textrm{mod}\ m)$으로 나타낼 수 있습니다.
페르마의 소정리를 이용하여 역원을 구하면 나눗셈을 곱셈으로 바꿀 수 있어서 편리하지만, 지수가 너무 커져서 거듭제곱 계산에 많은 시간이 들어갈 것으로 보입니다.
하지만, 여기서 $a^b\ \textrm{mod}\ c$를 빠르게 계산할 수 있는 테크닉이 있습니다.
바로 ‘분할 정복을 이용한 거듭제곱’이라고 하는 테크닉인데요, $$ a^n = \begin{cases} a^{\frac{n}{2}} \times a^{\frac{n}{2}} & \textrm{if } n\textrm{ is odd}\ \newline a^{\lfloor \frac{n}{2} \rfloor} \times a^{\lfloor \frac{n}{2} \rfloor} \times a & \textrm{if } n\textrm{ is even} \end{cases} $$ 위와 같이 $a^n$의 지수를 반으로 쪼개고, 구한 값을 바탕으로 다시 합치면, 거듭제곱 계산을 $\mathcal{O}(n)$에서 $\mathcal{O}(\lg n)$으로 줄일 수 있습니다! (여기서 $\lg$는 밑이 $2$인 로그, $\log _{2}$를 의미합니다.)
따라서, $m$이 소수일 때에는 분할 정복을 이용한 거듭제곱을 이용하여, $S_n\ \textrm{mod}\ m$을 $\mathcal{O}(\lg n)$에 구할 수 있습니다.
분할 정복
$m$이 만약 소수가 아니라면 어떨까요? 아쉽게도 여기서는 모듈로 곱셈 역원을 구하는 방법을 사용할 수 없습니다.
$a$와 $m$이 서로소가 아니라면, $aa^{\prime} \equiv 1\ (\textrm{mod}\ m)$을 만족하는 역원이 존재할 수 없기 때문입니다.
베주 항등식에 따르면, $ax + my$ 꼴로 표현할 수 있는 수는 $\gcd(a, m)$의 배수여야 하는데, $\gcd(a, m) \neq 1$이므로 당연히 $\gcd(a, m) \nmid 1$입니다. 따라서, $ax + my = 1$의 해가 존재하지 않으므로, 곱셈 역원이 존재하지 않습니다.
따라서, 합 공식을 사용하는 것은 불가능해보이고, 모든 항을 일일이 더하기에는 너무 느릴 것 같습니다.
그렇다면 $S_n$의 정의로 돌아가볼까요? $$ \begin{align*} S_n & = a_1 + a_2 + \cdots + a_n\ \newline & = a + ar + ar^2 + \cdots + ar^{n-1} \end{align*} $$ $S_n$을 풀어 헤쳐봤으니, 등비수열의 성질을 이용해 식을 간략하게 만들어봅시다.
먼저, $n$이 짝수일 때에는,
$$
\begin{align*}
S_n & =a+ar+ar^2+\cdots+ar^{n-1}\ \newline
& =(a+ar+\cdots+ar^{\frac{n}{2}-1})+(ar^{\frac{n}{2}}+ar^{\frac{n}{2}+1}+\cdots+ar^{n-1})\ \newline
& =(a+ar+\cdots+ar^{\frac{n}{2}-1})+ r^{\frac{n}{2}}(a+ar+\cdots+ar^{\frac{n}{2}-1})\ \newline
& =(a+ar+\cdots+ar^{\frac{n}{2}-1})(1+r^{\frac{n}{2}})\ \newline
& =S_{\frac{n}{2}}\cdot (1+r^{\frac{n}{2}})
\end{align*}
$$
이렇게 식의 규모를 딱 반으로 줄일 수 있습니다. 식이 반씩 줄어드니, 시간복잡도는 $\mathcal{O}(n)$에서 $\mathcal{O}(\lg n)$로 줄어들겠네요.
$(1+r^{\frac{n}{2}})$는 따로 ‘분할 정복을 이용한 거듭제곱’을 통해 $\mathcal{O}(\lg n)$에 구할 수 있습니다.
$n$이 홀수일 때에는 $S_n$을 정확히 반으로 묶어낼 수 없으므로, $$ \begin{align*} S_n & =(a+ar+\cdots+ar^{n-2})+ar^{n-1}\ \newline & =S_{n-1}+ ar^{n-1} \end{align*} $$ 으로 정리하고, $n-1$은 짝수이므로, $S_{n-1}$은 위의 짝수일 때의 경우를 이용하여 똑같이 처리하고, $ar^{n-1}$ 역시 ‘분할 정복을 이용한 거듭제곱’을 통해 $\mathcal{O}(\lg n)$에 구할 수 있습니다.
즉, $S_n$을 분할 정복을 이용하여 구하려면, $$ S_n = \begin{cases} S_{n-1}+ ar^{n-1} & \textrm{if } n\textrm{ is odd}\ \newline S_{\frac{n}{2}}\cdot (1+r^{\frac{n}{2}}) & \textrm{if } n\textrm{ is even} \end{cases} $$ 으로 표현할 수 있고, 시간복잡도는 $\mathcal{O}(\lg n)$이 됩니다!
요약
- $m$이 소수라면?
$S_n \equiv a(r^n -1)(r - 1)^{m - 2}\ (\textrm{mod}\ m)$ 이용.
- $m$이 소수인지에 관계없이,
$$ S_n = \begin{cases} S_{n-1}+ ar^{n-1} & \textrm{if } n\textrm{ is odd}\ \newline S_{\frac{n}{2}}\cdot (1+r^{\frac{n}{2}}) & \textrm{if } n\textrm{ is even} \end{cases} $$ 을 이용하여 $S_n\ \textrm{mod}\ m$을 $\mathcal{O}(\lg n)$에 구할 수 있습니다!
연습문제
BOJ 30413 - 양 한 마리… 양 A마리… 양 A제곱마리…
등비수열의 합을 $10^9+7$로 나눈 나머지를 구하는 문제입니다. 문제 조건에서, 춘배는 똑똑해서 $10^9+7$이 소수임을 알고 있다고 하니, 페르마의 소정리를 활용하여 쉽게 구할 수 있겠습니다. $r=1$인 상황을 주의합시다.
BOJ 15712 - 등비수열
이번에는 문제 입력으로 들어오는 $\textrm{mod}$가 소수라는 보장이 없습니다!
분할 정복으로 빠르게 구해봅시다.
BOJ 1160 - Random Number Generator
점화식 $X_{n+1} = (aX_n + c) \mod m$을 직접 손으로 적다 보면 중간에 등비수열이 하나 보입니다. 역시 $m$이 소수라는 보장이 없기 때문에, 분할 정복으로 합을 구해봅시다.