求出将1变成b的最少次数(不能变则输出-1)有两个操作。 1.将当前数字∗a 2.将当前数字循环右移一次(12345−>51234)
我们在看完题面之后,我们需要将数字1变成b。通过乘法或者循环右移,没有规律可言。注意到我们的数据范围(a,b)都是小于106。也就是我们把a变成大于min(106,b)之后这个状态是肯定没有用的。
状态只有106这么多,把两种操作看成是两条单向边。这样就变成了一个典型的最短路径问题。那么我们使用BFS(或者记忆化搜索)来解决。
本题为2024年10月19日小米机考原题
小米机考的介绍点击这里
小塔最近正在学习魔法,通过魔法可以改变纸上的数字。
小塔一共会两种魔法,第一种魔法可以将纸上数字变为它的a倍,比如在a=3时,他可以将666变成1998;第二种魔法可以让纸上的数字循环右移一次,比如12345在施加第二种魔法后会变成51234,119会变911,需要注意的是,小塔无法对小于10或是以0为结尾的数施加第二种魔法。
纸上的数字初始是1,小塔想将它变成自己的幸运数字b,那么请问小塔至少需要施加几次魔法。如果无论如何 都无法将它变成b,请输出−1。
输入一行,包含两个正整数a,b 2≤a,b<106
输出一行一个数,表示最少的魔法次数,或输出−1表示无解。
输入
3 621
输出
6
说明
样例解释1
一种可行的方法为:1−>3−>9−>27−>72−>216−>621
输入
3 666
输出
-1