题解 | #跳石板#

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {
    public static void main(String[] args) {
        //初始化一个数组，下标代表石板号，数组元素代表达到该石板的最小步数
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()){
        
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] num = new int [m+1];//从1到m
        //初始化数组元素位整数最大值
        for(int i=0;i<=m;i++){
            num[i] = Integer.MAX_VALUE;
        }
        //遍历数组，对数组元素进行赋值（到达的最小步数）
        //从n开始
        num[n] = 0;//让第一个为0
        for(int i=n;i<m;i++){
            //如果元素为最大值，就跳过
            if(num[i]==Integer.MAX_VALUE){
                continue;
            }
            //得到数组i下标的所有约数。然后给下标加约数的元素赋值
            List<Integer> list = qiuyue(i);

            for(int x: list){
                //取最小
                if(i+x<=m){
                    num[i+x] = Math.min(num[i+x],num[i]+1);
        
                }
            }

        }
        if(num[m]==Integer.MAX_VALUE){
            System.out.println(-1);
        }else {
            System.out.println(num[m]);
        }

    }
 }

    public static List<Integer> qiuyue(int n ){

        List<Integer> list = new ArrayList<>();
        for(int i=2;i*i <= n;i++){//此处必须要用优化的求约数方法不然通过不了
            if(n%i==0){
                list.add(i);
                if(n/i !=i){

                    list.add(n/i);
                }
            }
        }

        return list;

    }
    
}