Dac

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$을 빠르게 구할 방법을 소개하겠습니다....