题解 | #跳石板#

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

void get_div_num(int n, vector<int>& a) {
    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0)
        {
            a.push_back(i);
            if (n / i != i)
            a.push_back(n / 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(i, a);

        for (int j = 0; j < a.size(); ++j) {  
            if (a[j] + i <= m && step[a[j] + i] != INT_MAX)
                step[a[j] + i] = step[a[j] + i] < step[i] + 1 ? step[a[j] + i] : step[i] + 1;
            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, min_step;
    while (cin >> N >> M) {
        min_step = Jump(N, M);
        cout << min_step << endl;
    }
}