题解 | 将真分数分解为埃及分数

import math


def decompose_egyptian(a, b):
    res = []
    # 约分原始分数
    g = math.gcd(a, b)
    num = a // g
    den = b // g
    while num != 0:
        # 计算最小的k，使得1/k ≤ num/den → k ≥ ceil(den/num)
        k = (den + num - 1) // num  # 向上取整的技巧
        res.append(k)
        # 更新剩余分数：num/den - 1/k = (num*k - den)/(den*k)
        new_num = num * k - den
        new_den = den * k
        # 约分新分数
        g = math.gcd(new_num, new_den)
        num = new_num // g
        den = new_den // g
    return res


# 输入处理
s = input().strip()
a, b = map(int, s.split("/"))
result = decompose_egyptian(a, b)
print("+".join(f"1/{x}" for x in result))