#include <bits/stdc++.h>

using namespace std;

typedef long long ll; // 使用 long long 以处理较大的分母，避免溢出

// 计算最大公约数（GCD），用于约分分数
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b); // 辗转相除法
}

// 将分数 n/d 约分为最简形式
pair<ll, ll> reduce(ll n, ll d) {
    ll g = gcd(abs(n), d); // 计算 n 和 d 的 GCD，abs(n) 防止负数问题
    return {n / g, d / g}; // 返回约分后的分子和分母
}

// 表示埃及分数搜索状态的结构体
struct State {
    ll num, den; // 当前剩余分数 num/den
    vector<ll> dens; // 已选择的单位分数的分母列表

    // 计算当前状态的最大分母
    ll max_den() const {
        if (dens.empty()) return 0; // 如果没有分母，返回 0
        return *max_element(dens.begin(), dens.end()); // 返回分母列表中的最大值
    }
};

// 哈希函数，用于在 unordered_set 中存储状态（本实现未使用，但保留以备扩展）
struct StateHash {
    size_t operator()(const State& s) const {
        string str;
        for (ll x : s.dens) str += to_string(x) + ",";
        str += to_string(s.num) + "/" + to_string(s.den);
        return hash<string>()(str);
    }
};

// 获取当前状态的所有后继状态
vector<State> get_successors(const State& state, int limit, int depth) {
    vector<State> res; // 存储所有可能的后继状态
    ll r = state.num, s = state.den; // 当前剩余分数 r/s
    if (r == 0) return res; // 如果分子为 0，无需继续扩展

    // 确定最小分母：必须大于上一个分母（保证分母递增，避免重复），且满足 r/s >= 1/d
    ll last_d = state.dens.empty() ? 0 : state.dens.back();
    ll min_d = max(last_d + 1, (s + r - 1) / r); // min_d = ceil(s/r)

    // 设置分母的上限，防止过大的分母导致计算溢出
    const ll MAX_D = 10000000LL; // 合理的安全上限

    // 枚举可能的单位分母 d
    for (ll d = min_d; d <= MAX_D; ++d) {
        // 优化：检查剩余步数是否足够表示剩余分数
        int rem_steps = limit - depth - 1; // 剩余可用步数
        double max_sum_after = 0.0; // 剩余步数能表示的最大分数和
        for (int i = 1; i <= rem_steps; ++i) {
            max_sum_after += 1.0 / (d + i); // 假设后续分母递增
        }
        double this_contrib = 1.0 / d; // 当前单位分数的贡献
        double target = (double)r / s; // 目标剩余分数
        // 如果当前贡献加上后续最大可能贡献仍小于目标，剪枝
        if (this_contrib + max_sum_after < target - 1e-10) break;

        // 计算新分数：r/s - 1/d = (r*d - s) / (s*d)
        ll new_num = r * d - s;
        if (new_num < 0) continue; // 新分子为负，非法状态
        ll new_den = s * d;
        auto p = reduce(new_num, new_den); // 约分新分数
        State ns = {p.first, p.second, state.dens}; // 创建新状态
        ns.dens.push_back(d); // 添加当前单位分母
        res.push_back(ns); // 将新状态加入后继列表
    }
    return res;
}

// 深度优先搜索（DFS），在当前深度限制下搜索解
void dfs(const State& state, int depth, int limit, vector<State>& solutions) {
    if (depth > limit) return; // 超过深度限制，回溯
    if (state.num == 0 && !state.dens.empty()) { // 找到一个解：分子为 0 且有至少一个分母
        solutions.push_back(state); // 记录解
        return; // 不再扩展此路径
    }
    // 遍历所有后继状态
    for (const auto& next : get_successors(state, limit, depth)) {
        dfs(next, depth + 1, limit, solutions); // 递归搜索
    }
}

// 迭代加深搜索（IDS），寻找最短长度且最大分母最小的埃及分数
State find_best_egyptian(ll a, ll b) {
    auto p = reduce(a, b); // 约分输入分数
    State start = {p.first, p.second, {}}; // 初始状态
    State best; // 记录最佳解
    ll best_max = LLONG_MAX; // 最佳解的最大分母
    int limit = 0; // 当前深度限制

    while (true) {
        ++limit; // 增加深度限制
        vector<State> solutions; // 存储当前深度下的所有解
        dfs(start, 0, limit, solutions); // 执行 DFS
        if (!solutions.empty()) { // 如果找到解
            for (const auto& s : solutions) { // 遍历所有解
                ll cur_max = s.max_den(); // 当前解的最大分母
                if (cur_max < best_max) { // 如果最大分母更小，更新最佳解
                    best = s;
                    best_max = cur_max;
                }
            }
            return best; // 返回最佳解
        }
        if (limit > 100) { // 安全限制，防止无限循环
            cout << "No solution found within limit." << endl;
            exit(1);
        }
    }
}

int main() {
    ll a, b;
    // 输入分子和分母，要求 0 < a < b 且互质
    cout << "Enter numerator and denominator (a b, with 0 < a < b, gcd=1): ";
    cin >> a >> b;
    if (a >= b || a <= 0 || gcd(a, b) != 1) { // 简单输入验证
        cout << "Invalid input: require 0 < a < b and gcd(a,b)=1" << endl;
        return 1;
    }

    State result = find_best_egyptian(a, b); // 寻找最佳埃及分数

    // 输出结果
    cout << a << "/" << b << " = ";
    for (size_t i = 0; i < result.dens.size(); ++i) {
        if (i > 0) cout << " + ";
        cout << "1/" << result.dens[i]; // 打印单位分数
    }
    cout << endl;
    cout << "Length: " << result.dens.size() << endl; // 打印分解长度
    cout << "Max denominator: " << result.max_den() << endl; // 打印最大分母

    return 0;
}