本题为2024年10月19日小米机考原题
小米机考的介绍点击这里
题目内容
小红最近正在学习魔法，通过魔法可以改变纸上的数字。
题目大意
求出将1变成b的最少次数(不能变则输出-1)有两个操作。
1.将当前数字∗a
2.将当前数字循环右移一次(12345−>51234)
思路:单源BFS
我们在看完题面之后，我们需要将数字1变成b。通过乘法或者循环右移，没有规律可言。注意到我们的数据范围(a,b)都是小于106。也就是我们把a变成大于min(106,b)之后这个状态是肯定没有用的。
状态只有106这么多，把两种操作看成是两条单向边。这样就变成了一个典型的最短路径问题。那么我们使用BFS(或者记忆化搜索)来解决。
