2024.11.16#f(第六题)

· · 个人记录

QWQ

/*
第六题：神奇的计算机
输入n,m
输出n->m最少需要多少次操作
若无解，输出-1
每次操作(设这轮数为x):
3 4
1
2
4
输出
输入：3 18
9
18
输出：2 
x=x+x(*2)
x=x-x(归0)
x=x*x(*x)
x=x/x(归1)
*/
#include<bits/stdc++.h> 
using namespace std;
#define int long long
int n,m,ans=1e18;
void dfs(int cur,int i){//cur为当前经过i轮的数 
    if(cur>m)return ;
    if(m%cur!=0)return ;//m不是cur的整倍数 
    if(ans!=1e18&&i>=ans)return ;//当前使用次数>=当前答案,直接 return
    if(m==cur){//符合要求
        ans=min(ans,i);
        return ;
    }
    if((m/cur)%2!=0&&(m/cur)%cur!=0)return ;//不是二的偶数次幂且不能整除cur^2,直接 return
    if(cur!=1)dfs(cur*cur,i+1);
    dfs(cur*2,i+1);
    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    if(m==0||m==1){//归0||归一，一次
        cout<<1;
        return 0;
    }
    if(n==m){//特判相等
        cout<<0;
        return 0;
    }
    if(n==0&&m!=0){
        cout<<-1;
        return 0;
    }
    dfs(1,1);//归1，刚开始用了一次
    dfs(n,0);//不变，刚开始没用次数
    if(ans!=1e18)cout<<ans;
    else cout<<-1;
    return 0;
}//PS:这么简单的dfs+剪枝题我在考场上竟然没想出来！！！！！！