题目描述： 转换规则：如果数字d是x的约数，则x可以被转换为x+d。 现在给你两个正整数a和b，请你计算最少需要多少步能够将a转换成b。如果不能转换，则输出-1. 如：a = 1， b = 6, 则输出3.（1→2→4→6 或 1→2→3→6） note:测试数据已于2014年11月13日更新，以前通过的代码不一定能够再次通过。
示例： 输入： a = 1 b = 6 输出： 3
分析:
这个题目的意思就是要 把 a 变成 b。 转换规则就是： 如果数字d是x的约数，则x可以被转换为x+d。
定理一： 1 是 所有数的因数。 所以只要 a <= b, 那么a 就肯定可以转化为 b。每次 +1 。
定理二： 任意 1 个大于1的数n, 它的最大因数最大只能是 n // 2。 因此我们每次变化的时候，使 a = a * 2 并且满足 a <= b, 这样变化的趋势就是最快的。
我们先利用 定理二，快速找到一个 a，使得 a*2 < b。
然后再通过 a 的因数对a进行改变，最终使 a == b。
当然为了节约时间，我们 得到一个因数 tx 后，利用 a = tx * ty 得到 另外一个因数 ty, 从而节约一定的时间。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from queue import Queue
if a > b:
print(-1)
else:
res = 0
while 2*a < b:
a = a*2
res += 1
que = Queue()
set_a = set()
ans = {a: 0}
set_a.add(a)
que.put(a)
flag = True
while not que.empty() and flag:
ta = que.get()
for i in range(1, ta//2+1+1):
if not ta % i:
tx = ta + i
ty = ta + ta//i
if tx <= b:
if tx not in set_a:
ans[tx] = 999999
ans[tx] = min(ans[tx], ans[ta]+1)
set_a.add(tx)
que.put(tx)
if ty <= b:
if ty not in set_a:
ans[ty] = 999999
ans[ty] = min(ans[ty], ans[ta]+1)
set_a.add(ty)
que.put(ty)
if ty == b or tx == b:
flag = False
break
print(ans[b] + res)