网易28：跳石板

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

//求出n的所有非1和n的约数
/*
注意这里求约数的方法：以n的平方根为界限。先找出一个能整除的数，将除数放入约数数组中。
若判断除数不是他的平方根，再将对应的商放入数组中。
例如：24/2=12，此时n的界限为根号24，访问不到12，所以可以直接将除数与商放入数组中。
9/3=3，此时n的界限为3,只能将一个3放入数组中。
而且这样做了之后，约数数组中的数不是从大到小排列的，所以在下面得注意。
*/
void CommonDivision(int n, vector<int>& cd)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            cd.push_back(i);
            if (n / i != i)
                cd.push_back(n / i);
        }
    }
    //加上sort函数使其有序，下面判断越界的时候就不用全部遍历了，只用遍历不超过范围的前一部分即可
    sort(cd.begin(),cd.end());
}

/*
用矩阵dist[]表示n--m这一路每个点的可达性信息，存储到该点的最小距离；
若x从未被访问过，则dist[x]等于前一步的最小步数加1；若x被访问过，则dist[x]等于原值与前一步加1的最小值。
所以动态方程为dist[cd[j] + i] = min(dist[cd[j] + i], dist[i] + 1);
i为石板编号，j为i的约数
*/
int main()
{
    int n, m;
    cin >> n >> m;
    if (n == m)
    {
        cout << '0' << endl;
        return 0;
    }
    //建立表示步数的数组,范围0-m，初始化为0
    vector<int> dist(m + 1, 0);
    //循环求出从起点n到[n,m]范围内点的最小步数
    for (int d = n; d < m; d++)
    {
        //0表示这个点从前面的点不可到
        if (dist[d] == 0 && d != n)
            continue;

        //求出d的约数
        vector<int> cd;
        CommonDivision(d, cd);

        //对于d的每一个约数，逐个访问并更新从n到达他们的最小步数
        for (int i = 0; i < cd.size(); i++)
        {
            //要保证d+约数在m之内，否则会越界
            if (d + cd[i] <= m)
            {
                //若下一个点没有被访问过，则直接更新
                if (dist[d + cd[i]] == 0)
                    dist[d + cd[i]] = dist[d] + 1;
                //若下一个点已经被访问过，则取两者最小值
                else
                    dist[d + cd[i]] = min(dist[d + cd[i]], dist[d] + 1);
            }
            else
                break;

        }
    }
    if (dist[m] > 0)
        cout << dist[m] << endl;
    else
        cout << "-1" << endl;
    return 0;
}