C++(g++ 7.5.0) 解法, 执行用时: 63ms, 内存消耗: 23380K, 提交时间: 2022-08-03 11:16:03

#include<bits/stdc++.h>
using namespace std;
const int INF = 9999999;
#define LL long long
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
int N,M,K;
bool vis[201][200001];
struct data{
    int x,y,st;
}Que[20000001];
bool flag=false;
int l=1,r=1;
int ans;
void dfs(int a,int b,int c){
    if(a>b) swap(a,b);
    if(flag||a>200||b>20000) return ;
    if(!vis[a][b]){
        vis[a][b]=true;
        Que[++r].x=a,Que[r].y=b;
        Que[r].st=c;
        if(!flag&&(a==K||b==K)){
            flag=true;
            printf("%d\n",c);
        }
    }
}
void bfs(){
    Que[1].x=0,Que[1].y=1,Que[1].st=0;
    int step;
    while(l<=r){
        step=Que[l].st,N=Que[l].x,M=Que[l].y;
        dfs(N,N+N,step+1);
        dfs(N,M+M,step+1);
        dfs(M+M,M,step+1);
        dfs(N+N,M,step+1);
        dfs(N,M+N,step+1);
        dfs(N+M,M,step+1);
        dfs(M-N,M,step+1);
        dfs(N,M-N,step+1);
        l++;
        if(flag) return ;
    }
}
int main(){
    K=read();
    bfs();
    return 0;
}

C++ 解法, 执行用时: 106ms, 内存消耗: 10552K, 提交时间: 2022-04-17 20:56:43

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include <cctype>
#define my(a,b) if(n%__gcd(a,b)==0) q.push({-(sum+1+min(get(a),get(b))),{a,b}});
using namespace std;
int n;
map<pair<int,int>,bool> mp;
int get(int x) {
	int i;
	if(x<=n) {
		for(i=0; i<=20; i++) {
			if(x>=n) break;
			x*=2;
		}
		return i;
	} else {
		for(i=0; i<=20; i++) {
			if(x<=n) break;
			x/=2;
		}
		return i;
	}
}
int bfs() {
	priority_queue<pair<int,pair<int,int> > > q;
	if(n==1) return get(1);
	q.push({-min(get(0),get(1)),{1,0}});
	while(q.size()) {
		int a=q.top().second.first,b=q.top().second.second;
		int sum=-q.top().first-min(get(a),get(b));
		q.pop();
//		cout<<sum<<endl;
		if(a==n||b==n) return sum;
		if(mp[ {a,b}]) continue;
		mp[ {a,b}]=1;
		if(a) my(a,a+a);
		my(a+a,b);
		my(a,a+b);
		my(a+b,b);
		my(a,b+b);
		if(b) my(b+b,b);
		if(a<b) swap(a,b);
		my(a,a-b);
		my(a-b,b);
	}
    return -1;
}
int main() {
	cin>>n;
	cout<<bfs()<<endl;
	return 0;
}