题解 | 连分数

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

void solve(ll P,ll Q){
    cout<<P<<'/'<<Q<<" = ";
    ll y=P%Q;
    cout<<P/Q;
    ll cnt=0;
    while(y!=0){
        P=Q;
        Q=y;
        y=P%Q;
        if(y!=0){
            cout<<"+1/{";
            cnt++;
        }else{
            cout<<"+1/";
        }
        cout<<P/Q;
    }
    for(ll i=1;i<=cnt;i++){
        cout<<'}';
    }
    cout<<'\n';
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll T;
    cin>>T;
    while(T--){
        ll P,Q;
        cin>>P>>Q;
        solve(P,Q);
    }

    return 0;
}