题目内容

小塔最近正在学习魔法，通过魔法可以改变纸上的数字。

求出将 $1$ 变成 $b$ 的最少次数(不能变则输出-1)有两个操作。 1.将当前数字 $*a$ 2.将当前数字循环右移一次 $(12345->51234)$

我们在看完题面之后，我们需要将数字1变成b。通过乘法或者循环右移，没有规律可言。注意到我们的数据范围(a,b)都是小于 $10^6$ 。也就是我们把a变成大于min( $10^6$ ,b)之后这个状态是肯定没有用的。

状态只有 $10^6$ 这么多，把两种操作看成是两条单向边。这样就变成了一个典型的最短路径问题。那么我们使用BFS(或者记忆化搜索)来解决。

#P14048. 【广度优先搜索6】小塔爱魔法