Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 270 G問題 Sequence in mod P

AtCoder ABC270 ABC G問題 600 pts

問題

提出解答

問題の概要

次のようにして数列 $X=(X_i)_{i=0}^{\infty}$ が定められている.

$X_i=\begin{cases} S & (i=0) \\ (AX_{i-1}+B) \bmod{P} & (i \geq 1) \end{cases}$

このとき, $X_I=G$ となる非負整数 $I$ は存在するか? 存在するならばそのような $I$ の最小値を求めよ.

$T$ 個のマルチケース形式

制約

$1 \leq T \leq 100$
$2 \leq P \leq 10^9$
$P$ は素数
$0 \leq A,B,S,G \lt P$

解法

以降の解説では $\mathbb{Z}/P \mathbb{Z}$ の世界で考えることし, $X_i, A, B, S, T$ は全て $\mathbb{Z}/P \mathbb{Z}$ の元であるとする. このとき, $X_i$ は

$X_i=\begin{cases} S & (i=0) \\ AX_{i-1}+B & (i \geq 1) \end{cases}$

となる.

$A=[1 ]$ のとき, $X_i=Bi+S$ である. このとき,

$B \neq 0$ ならば, $G=X_I=BI+S \iff I=\dfrac{G-S}{B}$ である.
$B=0$ ならば, $G=S$ のときは答えは $0$ であり, $G \neq S$ の場合は存在しない.

$A=[0 ]$ のとき, $X_i$ は $i=0$ ならば $X_i=S$ , $i \geq 1$ ならば, $X_i=B$ である. よって,

$G=S$ ならば, 答えは $0$ である.
$G \neq S, G=B$ ならば, 答えは $1$ である.
$G \neq S, B$ ならば, 存在しない.

$A \neq [0], [1]$ とする. このとき, $\gamma:=\dfrac{B}{1-A}$ と定めると, $i \geq 0$ に対して, $X_i-\gamma=A(X_{i-1}-\gamma)$ が成り立つ. よって,

$X_i-\gamma=A^i (S-\gamma) \quad (i=0,1,2, \dots,)$

が成り立つ.

$S=\gamma$ の場合, $X_i=\gamma$ であるから, $G=S$ ならば, 答えは $1$ , そうでなければ存在しない.

$S \neq \gamma$ ならば, $\dfrac{G-\gamma}{S-\gamma}=A^i$ を満たすような $i$ の最小値を求めることになるが, これは離散対数問題である. よって, $O(\sqrt{P} \log P)$ 時間で求めることができる.

以上から, 1テストケースあたり $O(\sqrt{P} \log P)$ 時間で求めることができた.

なお, $I=\bullet$ の形式になっているパターンについては $\bullet$ における $0$ 以上 $P$ 未満の代表元となる整数がそのまま解答となる.