TIOJ 1040 C.連分數

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

std::vector<int> ans;
void gcd(int &x,int &y){
    int t,xx=x,yy=y;
    while(yy!=0){
        xx%=yy;
        int tt=xx;
        xx=yy;
        yy=tt;
    }
    x/=xx;
    y/=xx;
    return;
}
void ff(int n,int m){
    int tans=n/m;
    printf("%d",tans);
    n%=m;
    gcd(n,m);
    if(n==1){
        printf("+1/%d",m);
        return;
    }
    if(n==0)
        return;
    printf("+1/{");
    ff(m,n);
    printf("}");
}
int main(){
    int T;
    int n,m;
    scanf("%d",&T);
    while(T-->0){
        ans.clear();
        scanf("%d %d",&n,&m);
        printf("%d/%d = ",n,m);
        ff(n,m);
        printf("\n");
    }
}