题目大意

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

思路:单源BFS

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

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

P14345.【广度优先搜索8】小塔爱魔法

1000ms

Tried: 175

Accepted: 76

Difficulty: 5

算法与标签>BFS

本题为2024年10月19日小米机考原题

小米机考的介绍点击这里

题目内容

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

小塔一共会两种魔法，第一种魔法可以将纸上数字变为它的 $a$ 倍，比如在 $a=3$ 时，他可以将 $666$ 变成 $1998$ ;第二种魔法可以让纸上的数字循环右移一次，比如 $12345$ 在施加第二种魔法后会变成 $51234$ ， $119$ 会变 $911$ ，需要注意的是，小塔无法对小于 $10$ 或是以 $0$ 为结尾的数施加第二种魔法。

纸上的数字初始是 $1$ ，小塔想将它变成自己的幸运数字 $b$ ，那么请问小塔至少需要施加几次魔法。如果无论如何都无法将它变成 $b$ ,请输出 $-1$ 。

输入描述

输入一行，包含两个正整数 $a,b$ $2≤a,b<10^6$

输出描述

输出一行一个数，表示最少的魔法次数，或输出 $-1$ 表示无解。

样例1

输入

3 621

输出

说明

样例解释 $1$

一种可行的方法为: $1->3->9->27->72->216->621$

样例2

输入

3 666

输出

-1

输入

预期输出（选填）

题目大意

思路:单源BFS

P14345.【广度优先搜索8】小塔爱魔法

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About