组队竞赛

题目来源

牛客网：跳石板

题目描述

小易来到了一条石板路前，每块石板上从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号石板

输入描述

输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

输出描述

输出小易最少需要跳跃的步数,如果不能到达输出-1

示例1

输入

4 24

输出

5

思路分析

已知不能走1和当前石板号这两个约数
以4跳到24为例，从4号开始向后走，4号标记为0，表示跳到4号需要0步，从4号石板开始向后遍历，每到一个石板都标记当前石板能挑到的所有石板所需要的最少步数。

• 4号石板的约数为2，所以可以往前走2步，即标记6号石板为1，表示跳到6需要1步。
• 5号石板未被标记，因为从4号无法到5号，略过。
• 6号石板的约数为2和3，跳2步到8号，所以标记8号石板为1+1=2，前面的1表示跳到6号所需的最少步数，第二个1表示从6到8需要1步；跳3步到9号，与8号同理，标记9号也为2。
• 7号石板之前没有被标记过，表示之前的石板都无法跳到7号，略过。
• 8号石板的约数为2和4，且之前被标记为2，所以将10和12号石板标记为3。
• 9号石板约数为3，之前被标记为2，所以将12（9+3）号石板标记为3（2+1）。
• 10号石板约束为2和5，且之前被标记为3，本应将12和15号石板标记为4，但是由于之前8号石板对12标记了3，表明走8号石板跳到12号仅需要3步，比4小，取两次标记的较小值，所以12号石板标价仍为3，15号标记为4 。
• 11号石板未被标记，略过。
• 12号石板约束为2，3，4，6，且之前被标记为3，所以将14，15，16，18，分别标记为4。
  。。。。。。

依此类推，一直遍历到24号前一个石板。
最后24被标记的值即为从4跳到24所需的最少步数，如果未被标记，表示跳不到。
本题的核心思想就是从初始位置向后遍历，标记当前位置能跳到的所有石板的最少步数，而当前位置的标记也是之前位置跳到这里的最少步数，一直遍历到目的地，便得到了到达目标石板的最少步数。

代码展示

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
void GetDiv(int n, vector<int>& div)
{
    
    //i<=sqrt,注意加等号
    for (int i = 2; i <= sqrt(n); i++)
    {
    
        if (n % i == 0)
        {
    
            div.push_back(i);
            if (n / i != i)
            {
    
                div.push_back(n / i);
            }
        }
    }
}
int main()
{
    
    int n, m;
    while (cin >> n >> m)
    {
    
        //用m初始化v
        vector<int> v(m + 1, m);
        v[n] = 0;
        vector<int> div;//保存约数
        while (n < m)
        {
    
            if (v[n] != m)
            {
    
                div.clear();
                GetDiv(n, div);
                //遍历保存约数的动态数组
                for (int i = 0; i < div.size(); i++)
                {
    
                    //判断是否越界，注意加等号
                    if (n + div[i] <= m)
                    {
    
                        //动态数组的每个元素都被初始化为m,m的值一定大于当前的步数
                        //比较本次加1后的步数和原来步数，取较小的值
                        v[n + div[i]] = v[n] + 1 < v[n + div[i]] ? v[n] + 1 : v[n + div[i]];
                    }
                }
            }
            n++;
        }
        if (v[m] != m)
        {
    
            cout << v[m] << endl;
        }
        else
        {
    
            cout << -1 << endl;
        }
    }
    system("pause");
    return 0;
}