Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int oo = 1000000009;
using namespace std;
int n, t;

int GCD(int a, int b) {
    if (a == 1) return b - 1;
    if (b == 1) return a - 1;
    if (a % b == 0) return oo;
    return (GCD(b, a % b) + a / b);
}

int Cal(int n) {
    int res = oo, lim = (n+1)/2;
    for(int i=1; i<=lim; i++)
        res = min(res, GCD(i, n));
    return res;
}

int main()
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", Cal(n));
    }
    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
const int INF=(int)1e9+7;
inline void minimize(int &x,const int &y) {
    if (x>y) x=y;
}
inline int nextint(void) {
    int x;
    scanf("%d",&x);
    return (x);
}
int steps(int a,int b,int lim) {
    int res=0;
    while (true) {
        if (res>=lim) return (lim);
        if (a==0 || b==0) return (INF);
        if (a==1 && b==1) return (res);
        res++;
        if (a>b) a-=b; else b-=a;
    }
}
int answer(int x) {
    int best=INF;
    REP(i,x) minimize(best,steps(x,i+1,best));
    return (best);
}
int main(void) {
    REP(zz,nextint()) printf("%d\n",answer(nextint()));
    return 0;
}