[Luogu 2090]数字对

Description

对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。

给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。

Input

第一行一个正整数 n

Output

一个整数表示答案。

Sample Input

Sample Output

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 ;

 }

巴特西