题解 | 连分数

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


void dfs(int p,int q)
{

    int a = p/q;
    int r = p%q;
    p = r;
    swap(p,q);
    if(p!=1&&q!=0)cout<<"{";
    cout<<a;
    if(p!=1&&q!=0)
    {   cout<<"+1/";
        dfs(p,q);
        cout<<"}";
    }
}

void solve()
{
    ll p,q;
    
    cin>>p>>q;

    cout<<p<<"/"<<q<<" = ";
    int a = p/q;
    int r = p%q;
    p = r;
    swap(p,q);
    cout<<a;
    if(p!=1&&q!=0)
    {
        cout<<"+1/";
        dfs(p,q);
    }
    cout<<'\n';

}


int main() {
    int t;
    cin>>t;
    while (t--) 
    {
        solve();
    }
}

细节挺多的递归题