题解 | #连分数#

该问题最适合采用迭代或递归式的欧几里得算法（Euclidean Algorithm）。连分数的每一层系数项 正好对应于执行 时的整数商。

对于分数 ：

1. 令 ，余数 。
2. 。
3. 重复上述过程处理 ，直到余数为 0。

• 整除情况：如果初始 ，则只需输出 的商，无需后续的 结构。
• 终止条件：当当前分母能被分子整除时，最后一段不再产生新的分数嵌套。例如 7/3 变为 2 + 1/3 而非 2 + 1/{3 + 1/{...}}。

复杂度分析

• 时间复杂度：。 连分数的项数等同于欧几里得算法的步数。根据拉梅定理（Lamé's Theorem），辗转相除法的步数与输入数字的位数呈线性关系，即对数级增长。
• 空间复杂度：。 由于需要构造嵌套字符串，递归调用的深度或存储系数的栈空间与步数一致。

代码实现

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

void solve(ll P, ll Q) {
    ll k = P / Q;
    ll r = P % Q;

    cout << k;
    if (r != 0) {
        if (Q % r == 0)
            cout << "+1/" << Q / r;
        else {
            cout << "+1/{";
            solve(Q, r);
            cout << "}";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;

    while (T--) {
        ll P, Q;
        if (cin >> P >> Q) {
            cout << P << "/" << Q << " = ";
            solve(P, Q);
            cout << "\n";
        }
    }
    return 0;
}