题目描述: 转换规则:如果数字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)