Description
对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。
给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。
Input
第一行一个正整数 n
Output
一个整数表示答案。
Sample Input
5
Sample Output
3
Hint
样例解释：
(1,1) → (1,2) → (3,2) → (5,2)
对于30%的数据， 1 <= n <= 1000
对于60%的数据， 1 <= n <= 20000
对于100%的数据，1 <= n <= 10^6
题解
我们注意到对于数对$(x,y)$，$x>y$，一定是由$(x-y,y)$推得的，我们发现就是更相减损术。
我们可以枚举$<n$的所有数，做一遍$gcd$，统计操作次数。
最终，如果其中一个数为$1$,那么我们可以去更新一下答案；
但如果为$0$，即最初始数对不合法，舍去。
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; int n,cnt;
int gcd(int a,int b)
{
int cnt=;
while (true)
{
if (b==) return ;
if (b==)
{
cnt+=a-;
break;
}
cnt+=a/b;
a%=b;
swap(a,b);
}
return cnt;
} int main()
{
scanf("%d",&n);
int ans=~0u>>;
if (n==) printf("0\n");
else
for (int i=;i<n;i++)
{
int cnt=gcd(n,i);
if (cnt) ans=min(ans,cnt);
}
printf("%d\n",ans);
return ;
}