记录编号	604807	评测结果	AAAAAAAAAA
题目名称	3451.Power Calculus	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	1.306 s
提交时间	2025-08-11 21:25:13	内存使用	3.71 MiB

#include<iostream>
using namespace std;

int n, deep;
int gcd(int a, int b){
	return (!b) ? a : gcd(b, a % b);
}

bool dfs(int x, int a, int b){
	if(a == b) return false;
    if(x == deep + 1) return false;
    if(a > b) swap(a, b);
    if((b << (deep - x)) < n) return false;
    if(n % gcd(a, b)) return false;
    if(b == n) return true;
    if(dfs(x + 1, b + b, b)) return true;
    if(dfs(x + 1, b - a, b)) return true;
    if(dfs(x + 1, a + a, b)) return true;
    if(dfs(x + 1, a + b, b)) return true;
	if(dfs(x + 1, a, b + b)) return true;
    if(dfs(x + 1, a, b - a)) return true;
    if(dfs(x + 1, a, a + a)) return true;
    if(dfs(x + 1, a, a + b)) return true;
    return 0;
}

int main(){
	freopen("pow_cal.in","r",stdin);
	freopen("pow_cal.out","w",stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
	while(cin >> n){
		if(n == 0) return 0;
		for(int i = 0;;i ++){
			deep = i;
			if(dfs(0, 0, 1)){
				cout << deep << '\n';
				break;
			}
		}
	}
	return 0;
}