牛客网 跳石板

输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

输出小易最少需要跳跃的步数,如果不能到达输出-1

4 24

5

N,M=[int(each) for each in input().split()]

def getNYueShu(n):
    mid=n//2
    result=[]
    for i in range(2,mid+1):
        if i not in result:
            # 判断是否是约数
            if n%i==0:
                result.append(i)
                j=int(n/i)
                if j not in result:
                    result.append(j)
    return result


def getCounts(N,M):
    # ys=getNYueShu(N)
    # ys=sorted(ys,reverse=True)
    count=0
    step=[-1]*(M+1)
    step[N]=0
    cur_val=[N]
    while cur_val:
        next=[]
        count+=1
        #print(count)
        for j in cur_val:
            ys=getNYueShu(j)
            ys = sorted(ys, reverse=True)
            for i in ys:
                if j+i<=M and i+j not in next:
                    next.append(i+j)
        tmp_next=[]
        for n in next:
            if step[n]==-1:
                step[n]=count
                tmp_next.append(n)
                if n==M:
                    break

        cur_val=tmp_next
    return step[M]


print(getCounts(N,M))

def solution(n, m):
    divs = [[] for _ in range(m + 1)]
    for i in range(2, m + 1):
        t=[j for j in range(i + i, m + 1, i)]
        for j in range(i + i, m + 1, i):
            divs[j].append(i)

    value = [m] * (m + 1)
    value[n] = 0
    for i in range(n, m + 1):
        if value[i] < m:
            for x in divs[i]:
                if i + x < m + 1:
                    value[i + x] = min([value[i + x], value[i] + 1])
    if value[m] < m:
        return value[m]
    else:
        return -1


data = [int(i) for i in input().strip().split()]
n = data[0]
m = data[1]

print(solution(n, m))