この問題は、整数を頂点として、 \(u\) から \(v\) に数を変化されられるときに \(u \to v\) に有向辺を貼ると、重みなしグラフの頂点 \(1\) から頂点 \(N\) への最短路を計算する問題に帰着します。
重みなしグラフの最短路は幅優先探索 (BFS) を用いて計算できることが知られています。特にこの問題の場合は、グラフの頂点数を \(V\)、辺の本数を \(E\) として

• \(1\) 個の頂点から伸びる辺の本数は高々 \(2\) 本なので \(\frac{V}{2} \leq E \leq V\) である。
• 頂点 \(n\) から行ける頂点を求めるのに \(\mathrm{O}(\log n)\) の計算量がかかる。

ことから、訪問する頂点番号の最大値を \(M\) として計算量は \(\mathrm{O}(M \log M)\) となります。

よってこの問題を解けました…と言いたいところですが問題はグラフの頂点数 \(V\) で、なんの制約もないと頂点数は \(\infty\) になってしまうので計算量も \(\mathrm{O}(\infty)\) になってしまいます。よって訪問するグラフの頂点になんらかの制限をつける必要があります。

この問題は \(1\) から \(N\) までの最短パスを知りたいのを思い返すと、\(1\) から \(N\) へのパスに登場する数字以外は調べなくてよいということが分かります。
\(1\) から \(N\) へのパスに登場する数字は最大でいくつでしょうか？これはいくつかの観察から求めることができます。

観察 \(1\)

現在の数の桁数を \(A\) 桁とすると、操作によって変化した後の数の桁数は \(A\) 桁以上である。

\(1\) 個目の操作では書かれてる数は \(a\) 倍される、すなわち大きくなるので桁数も同じか大きくなります。
2 個目の操作は 長さ \(N\) の文字列の末尾を先頭に持ってくる操作なので桁数は \(A\) 桁のままです。
よって、どちらの操作でも桁数は \(A\) 桁より小さくならないことが確認できます。

観察 \(2\)

\(1\) から \(N\) までに変化するまでの操作列の中で出てくる数字は高々 \(A\) 桁の数しか登場しない。

例えば \(a = 5, N=52562\) の場合

• \(1 \to 5\to 25\to 125\to 512\to 251\to 1255\to 5125\to 25625 \to 52562\)

と変化しますが、このとき桁数の列は

• \(1\to 1\to 2\to 3\to 3\to 3\to 4\to 4\to 5 \to 5\)

となり、たしかに \(N\) と同じ桁数かそれ以下の桁数の数字しか登場していません。

これは観察 \(1\) から証明できます。観察 \(1\) より桁数の列は単調増加であることがわかり、また、列の末尾は \(A\) なので、桁数の列に登場する数は \(A\) 以下です。

以上の \(2\) つの観察により、調べる範囲は \(N\) の桁数を \(A\) として 桁数が \(A\) 以下である数字 であることがわかりました。

よって、グラフ上で訪問する頂点番号の最大値を \(M\) とすると、\(10N\) は \(A + 1\) 桁の数であることから \(M \lt 10N\) が従うので \(M = \mathrm{O}(N)\) であるとわかります。よってこの問題を \(\mathrm{O}(N \log N)\) で解くことができました。(なお、 BFS を動作させたときの訪問する頂点数は \(M\) よりもはるかに小さいのでアルゴリズムの定数倍は軽いです。)

別解として、辺の向きを逆向きにして \(N\) を始点、\(1\) を終点として BFS する方法もあります。こちらの場合でも上記の計算量解析を適用することができて、 \(\mathrm{O}(N \log N)\) で解くことができます。

Python による実装は次の通りです。

from collections import deque

a, N = map(int, input().split())

M = 1
while M <= N:
  M *= 10

d = [-1] * M
Q = deque()
d[1] = 0
Q.append(1)

while len(Q):
  c = Q.popleft()
  dc = d[c]

  op1 = a * c
  if op1 < M and d[op1] == -1:
    d[op1] = dc + 1
    Q.append(op1)

  if c >= 10 and c % 10 != 0:
    s = str(c)
    op2 = int(s[-1] + s[:-1])
    if op2 < M and d[op2] == -1:
      d[op2] = dc + 1
      Q.append(op2)

print(d[N])