题解 | #跳石板#

#include <iostream>
#include<cmath>
#include<vector>
#include<climits>
using namespace std;

void get_div_num(vector<int>& a, int x) {
    for (int i = 2; i <= sqrt(x); ++i) {
        if (x % i == 0) {
            a.push_back(i);
            if (x / i != i)
                a.push_back(x / i);
        }
    }
}

int Jump(int n, int m) {
    vector<int> step(m + 1, INT_MAX);
    step[n] = 0;
    for (int i = n; i < m; ++i) {
        if (step[i] == INT_MAX)
            continue;
        vector<int> a;
        get_div_num(a, i);
        for (int j = 0; j < a.size(); j++) {
            if(i + a[j] <= m && step[i + a[j]] != INT_MAX) {
                //新的和旧的比较谁的步数少
                step[i + a[j]] = step[i + a[j]] > step[i] + 1 ? step[i] + 1 :step[i + a[j]];
            } else if (a[j] + i <= m) {
                step[a[j] + i] = step[i] + 1;
            }
        }
    }
    return step[m] == INT_MAX ? -1 : step[m];
}

int main() {
    int n, m;
    int min_step = 0;
    while (cin >> n >> m) {
        min_step = Jump(n, m);
        cout << min_step << endl;
    }
    return 0;
}