ZR#1012

## ZR#1012

blog咕咕咕了好久，开始补。

解法：

一个很显然的性质， $ x $ 只能转移到 $ x+1 $ 或者 $ 2x $ 处，所以我们可以以此性质建图，即 $ x $ 向 $ x + 1 $ 和 $ 2x $ 处连边，然后跑一遍SPFA就行了，建图过程详见代码。

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>

using namespace std;

#define INF 2147483647
const int N = 1e6 + 100;

int dis[N],x,n;
bool vis[N];
queue<int> q;

inline void calc(int v,int u,int val) {
	if(dis[v] > dis[u] + val) {
		dis[v] = dis[u] + val;
		if(!vis[v]) q.push(v),vis[v] = true;
	}
}
inline void spfa() {
	while(!q.empty()) {
		int v = q.front();
        q.pop();
		if(v < n) calc(v + 1,v,1);
		if(v > 0) {
			calc(v - 1,v,1);
			for(int i = 1 ; v * i <= n ; i++) {
				if(v * (i + 1) > n) calc(n,v,2 * i + 4 + v * (i + 1) - n);
				else calc(v * (i + 1),v,2 * i + 4);
			}
		}
		vis[v] = false;
	}
}

int main() {
    scanf("%d%d",&x,&n);
    for(int i = 0 ; i <= n ; i++) dis[i] = INF;
	if(x > n) {
		dis[0] = 3,dis[n] = x - n;
		vis[x] = vis[n] = vis[0] = true;
		q.push(0);
        q.push(n);
	} else {
		dis[x] = 0;
        vis[x] = 1;
		q.push(x);
	}
	spfa();
	printf("%d
",dis[n]);
    //system("pause");
	return 0;
}