【描述】

给一个数对$(a,b)$，那么$(a,b)$可以变成$(a,a+b)$或$(a+b,b)$。

初始数对$(1,1)$，求要变换几次可以使一个数变为$n$。

$n \leq 1000000$

【样例】

Input: 5

Output: 3

【题解】

逆推，$(a,b)$可以推到$(a-b,b) iff (a>b)$,$(a,b-a) iff(b>a)$。

枚举$(i,n)$，逆推即可。时间复杂度$O(n \times ???)$ 据说$???=log_{2}n$

# include <stdio.h>
# include <algorithm>
using namespace std;

const int INF=2333333;
int n,ans;

inline int c(int a,int b) {
	int res=0;
	while(a!=1||b!=1) {
		if(b==a)return INF;
		b-=a;++res;
		if(a>b) {
			int t=a;
			a=b;
			b=t;
		}
	}
	return res;
}

int main() {
	freopen("numpair.in","r",stdin);
	freopen("numpair.out","w",stdout);
	scanf("%d",&n);
	ans=INF;
	for (int i=1;i<n;++i) ans=min(ans,c(i,n));
	printf("%d\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}