题解 | 连分数

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;cin>>T;
    while(T--)
    {
        int p,q;
        cin>>p>>q;
        int cnt=0;
        cout<<p<<"/"<<q<<" = "<<p/q;
        while(p%q)
        {
            cout<<"+1/";
            int t=q;
            q=p%q;
            p=t;
            if(p%q) cout<<"{";
            cout<<p/q;
            if(p%q) ++cnt;
        }
        while(cnt--) cout<<"}";
        cout<<endl;
    }
    return 0;
}