Kazun の競プロ記録

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

AtCoder Beginner Contest 235 D 問題 Multiply and Rotate

AtCoder ABC ABC235 D問題 400 pts

問題

提出解答

問題の概要

整数 $x$ に対して, 以下の操作を行い, $x$ を更新していく.

$x \gets ax$
$x \geq 10$ で, $x$ が $10$ の倍数ではないとき, $x$ の末尾の数字を先頭に移動させる.

最初, $x=1$ であるが, 操作を繰り返すことにより, $x=N$ にすることは可能か? 可能ならば操作回数の最小値を求めよ.

制約

$2 \leq a \lt 10^6$
$2 \leq N \lt 10^6$

解法

次の有向グラフ $D=(V,A)$ を構成する.

$V$ は正の整数全体の集合
$A=\{(x,ax) \mid x \in V \} \cup \{(x,f(x)) \mid x \in V, x \geq 10, 10 \not| x \}$ . ただし, $f(x)$ は $x$ の末尾の数字を先頭に移動させた整数.

このグラフ $D$ において, $1$ と $N$ の距離が答えになる.

ここで, このまま解くと, $D$ は無限グラフになってしまう. しかし, 操作について, 操作前の桁数と操作後の桁数について, 減ることは無い. よって, $N$ の桁数を $d$ として, $W:=\{1,2, \dots, 10^d-1\}$ として, $A$ の $W$ による誘導部分グラフ $A[W]$ についてのみ見れば十分である.

距離は $A[W]$ 上の BFS で求めることができ, 計算量は $O(N \log N)$ *1 *2になる.

*1: $\log$ は $f(x)$ を求める際にかかる.

*2:定数倍も込めるなら, $O(10N \log N)$ になる.