题解 | #连分数#

思考过程

这题看上去是“格式化输出”，但核心其实是数学： 有穷连分数的每一项，就是辗转相除法每一步的商。

所以第一反应不应该是去“硬拼式子”，而是先把分数拆成连分数系数序列。

以 P/Q 为例：

1. 先取整 a0 = P / Q
2. 余数 r = P % Q
3. 如果 r = 0，break 出循环
4. 否则令 P = Q, Q = r，继续下一轮

这样得到一个序列 a0, a1, ..., ak，对应连分数： a0+1/{a1+1/{a2+...+1/ak}}

解题思路

可以分成两段做：

1. 求系数序列

• 用辗转相除法循环
• 每轮把 P/Q 的商丢进数组
• 直到余数为 0

2. 从后往前构造表达式

• 初始字符串 s = 最后一个系数
• 倒着枚举前面的系数 ai
• 更新为 ai + 1 / (当前s) 的结构
• 但注意输出格式要求是花括号：+1/{...}

输出格式的关键点

这题最容易错在这里：

• 当分母是一个纯数字时，应该写 +1/3，不是 +1/{3}
• 当分母是一个复合表达式时，才需要花括号：+1/{2+1/3}

也就是：

• 分母里有 +，加 {}
• 分母里没 +，直接用数字

复杂度

每组数据就是一遍欧几里得算法，复杂度 O(log(min(P,Q)))。
T 组数据总复杂度是 O(T log(min(P,Q)))，ez。

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

using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vll=vector<ll>;
using vvll=vector<vector<ll>>;
using vc=vector<char>;
using vs=vector<string>;
using vb=vector<bool>;
using vpii=vector<pii>;
using vpll=vector<pll>;

const int INF=1e9;
const ll LINF=4e18;
const int MOD=1e9+7;
const int MOD2=998244353;

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ral(x) x.rbegin(),x.rend()
#define fi first
#define se second
#define fix(x) fixed<<setprecision(x)

ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}

ll qpow(ll a,ll b,ll mod=MOD){
	ll res=1;
	a%=mod;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

ll modinv(ll a,ll p=MOD){
	return qpow(a,p-2,p);
}

struct Node{
	int a,b;
	
	bool operator<(const Node &y)const{
		return b>y.b;
	}
};

void solve(){
    ll p,q;cin>>p>>q;
    ll x=p,y=q;
    vll a;
    while(1){
        a.push_back(p/q);
        ll r=p%q;
        if(r==0)break;
        p=q;
        q=r;
    }
    string s=to_string(a.back());
    for(int i=(int)a.size()-2;i>=0;--i){
        string t=s;
        if(t.find('+')!=string::npos)t="{"+t+"}";
        s=to_string(a[i])+"+1/"+t;
    }
    cout<<x<<"/"<<y<<" = "<<s<<endl;
}

int main(){
	IOS;
	int _=1;cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

神了，两次想自测都点到提交