题解 | 跳石板

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // 获取数字n的所有约数(不包括1和自身)
    vector<int> getDivisors(int n) {
        vector<int> divs;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                divs.push_back(i);
                if (i * i != n) {
                    divs.push_back(n / i);
                }
            }
        }
        return divs;
    }
    
public:
    int minJumps(int N, int M) {
        vector<int> dist(M + 1, -1);  // 存储到达每个位置的最小步数
        queue<int> q;
        
        // 初始位置
        q.push(N);
        dist[N] = 0;
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            
            // 找到目标位置
            if (curr == M) return dist[curr];
            
            // 获取当前位置的所有约数作为可能的跳跃步数
            vector<int> steps = getDivisors(curr);
            
            // 尝试所有可能的跳跃
            for (int step : steps) {
                int next = curr + step;
                if (next <= M && dist[next] == -1) {
                    dist[next] = dist[curr] + 1;
                    q.push(next);
                }
            }
        }
        
        return -1;  // 无法到达目标位置
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    
    Solution sol;
    cout << sol.minJumps(N, M) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        // 获取数字n的所有约数(不包括1和自身)
        private List<Integer> getDivisors(int n) {
            List<Integer> divs = new ArrayList<>();
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) {
                    divs.add(i);
                    if (i * i != n) {
                        divs.add(n / i);
                    }
                }
            }
            return divs;
        }
        
        public int minJumps(int N, int M) {
            int[] dist = new int[M + 1];
            Arrays.fill(dist, -1);
            Queue<Integer> q = new LinkedList<>();
            
            // 初始位置
            q.offer(N);
            dist[N] = 0;
            
            while (!q.isEmpty()) {
                int curr = q.poll();
                
                if (curr == M) return dist[curr];
                
                // 获取所有可能的跳跃步数
                List<Integer> steps = getDivisors(curr);
                
                // 尝试所有可能的跳跃
                for (int step : steps) {
                    int next = curr + step;
                    if (next <= M && dist[next] == -1) {
                        dist[next] = dist[curr] + 1;
                        q.offer(next);
                    }
                }
            }
            
            return -1;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        Solution sol = new Solution();
        System.out.println(sol.minJumps(N, M));
        
        sc.close();
    }
}

from collections import deque
from typing import List

class Solution:
    def get_divisors(self, n: int) -> List[int]:
        """获取数字n的所有约数(不包括1和自身)"""
        divs = []
        i = 2
        while i * i <= n:
            if n % i == 0:
                divs.append(i)
                if i * i != n:
                    divs.append(n // i)
            i += 1
        return divs
    
    def min_jumps(self, N: int, M: int) -> int:
        dist = [-1] * (M + 1)  # 存储到达每个位置的最小步数
        q = deque([N])
        dist[N] = 0
        
        while q:
            curr = q.popleft()
            
            if curr == M:
                return dist[curr]
            
            # 获取所有可能的跳跃步数
            steps = self.get_divisors(curr)
            
            # 尝试所有可能的跳跃
            for step in steps:
                next_pos = curr + step
                if next_pos <= M and dist[next_pos] == -1:
                    dist[next_pos] = dist[curr] + 1
                    q.append(next_pos)
        
        return -1  # 无法到达目标位置

def main():
    N, M = map(int, input().split())
    
    sol = Solution()
    print(sol.min_jumps(N, M))

if __name__ == "__main__":
    main()