#include#include #include using namespace std; //计算第i个的全部余数 //因为复杂度限制 所以值遍历到平方的位置 void getsum(int n, vector<int>& v) { for (int i = 2; i ) { if (n % i == 0) { v.push_back(i); //如果他是 2*2=4这种 那么就只算一个约数 如果是2*3=6 那么两个都要算入6的约数 if (n / i != i) { v.push_back(n / i); } } } } int bs(int n, int m) { //开24个 是0~23 m为24 所以要实际要开25个 vector<int> v(m + 1, 0);//全部置为0 //记住这个v是全部初始化为0 v里记的是步数 //初始位置置为1 v[n] = 1; for (int i = n; i < m; i++) { //这里的i是第几个 而不是单纯为了循环几次 if(v[i]==0) continue; vector<int> v2; getsum(i, v2); for (int j = 0; j < v2.size(); j++) { //约数+实数 k+x 小于m时 并且v中已经存在了步数 那么保留最小步数 //2+6 if (v2[j] + i 0 ) { //在2+6这个位置 选出最小步数 v[v2[j] + i] = v[v2[j] + i] < v[i] + 1 ? v[v2[j] + i] : v[i] +1; } //如果这里没步数 那么就是0+1 因为里面全部初始化为0 else if (v2[j] + i m) { v[v2[j] + i] = v[i]+1; } } } return v[m] == 0 ? -1 : v[m]-1;//因为开头在n的位置初始化为1 后续+1步数 多添了1个 所以要在最后-1 } int main() { int n, m; while (cin >> n >> m) { cout << bs(n, m); } return 0; }
Original: https://www.cnblogs.com/LonelyMoNan/p/16753987.html
Author: lemon-Breeze
Title: 跳石板—牛客网
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/607379/
转载文章受原作者版权保护。转载请注明原作者出处！