算乘方的牛--距离***搜索还有3题

题解在b站,id:shyyhsac

#include <bits/stdc++.h>
using namespace std;
int n;
bool dfs(int x,int y,int dep)//假设第一个工作变量大于第二个工作变量.
{
    if(dep==0) return  x==n;
    //剪枝1:
    if(x<<(dep)<n)  return false;
    //剪枝2:
    if(n%(__gcd(x,y))!=0) return false;
    int a,b;
    a=x+x;b=x;
    if(b&&dfs(a,b,dep-1)) return true;
    a=x+x;b=y;
    if(b&&dfs(a,b,dep-1)) return true;
    a=x+y;b=x;
    if(b&&dfs(a,b,dep-1)) return true;
    a=x+y;b=y;
    if(b&&dfs(a,b,dep-1)) return true;
    a=y+y;b=y;
    if(b&&dfs(a,b,dep-1)) return true;
    a=y+y;b=x;if(a<b) swap(a,b);
    if(b&&dfs(a,b,dep-1)) return true;
    a=x-y;b=x;
    if(b&&dfs(a,b,dep-1)) return true;
    a=x-y;b=y;if(a<b) swap(a,b);
    if(b&&dfs(a,b,dep-1)) return true;
    return false;
}

int main()
{
    cin>>n;
    int depth=0;
    while(!dfs(1,0,depth)) depth++;
    cout<<depth<<endl;
    return 0;
}