問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$\displaystyle \sum_{i=0}^{X-1} A^i$ を $M$ で割った余りを求めよ.

制約

$1 \leq A,M \leq 10^9$
$1 \leq X \leq 10^{12}$

解法

$\displaystyle S_x:=\sum_{i=0}^{x-1} A^i$ とおく. このとき, 求めるべきは $S_X$ である.

$x=1$ のとき $\displaystyle S_1=\sum_{i=0}^0 A^i=1$ となる.

$x$ が $3$ 以上の奇数のとき, $S_x=S_{x-1}+A^{x-1}$ である *1.

$x$ が偶数のとき

$\begin{align*} S_x &=\sum_{i=0}^{x-1} A^i \\ &=\sum_{i=0}^{\frac{x}{2}-1} A^i+\sum_{i=\frac{x}{2}}^{x-1} A^i \\ &=\sum_{i=0}^{\frac{x}{2}-1} A^i+\sum_{j=0}^{\frac{x}{2}-1} A^{\frac{x}{2}+j} \\ &=\sum_{i=0}^{\frac{x}{2}-1} A^i+A^{\frac{x}{2}} \sum_{j=0}^{\frac{x}{2}-1} A^j \\ &=\left(1+A^{\frac{x}{2}} \right) \sum_{i=0}^{\frac{x}{2}-1} A^i \\ &=\left(1+A^{\frac{x}{2}} \right) S_{\frac{x}{2}} \end{align*}$

となる.

よって,

$S_x=\begin{cases} 1 & (x=1) \\ S_{x-1}+A^{x-1} & (x \geq 3, x: \text{odd}) \\ \left(1+A^{\frac{x}{2}} \right) S_{\frac{x}{2}} & (x: \text{even}) \end{cases}$