题解在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; }