AtCoder Beginner Contest 235 D 問題 Multiply and Rotate
問題
提出解答
問題の概要
整数 に対して, 以下の操作を行い,
を更新していく.
で,
が
の倍数ではないとき,
の末尾の数字を先頭に移動させる.
最初, であるが, 操作を繰り返すことにより,
にすることは可能か? 可能ならば操作回数の最小値を求めよ.
制約
解法
次の有向グラフ を構成する.
は正の整数全体の集合
. ただし,
は
の末尾の数字を先頭に移動させた整数.
このグラフ において,
と
の距離が答えになる.
ここで, このまま解くと, は無限グラフになってしまう. しかし, 操作について, 操作前の桁数と操作後の桁数について, 減ることは無い. よって,
の桁数を
として,
として,
の
による誘導部分グラフ
についてのみ見れば十分である.