题解 | #将真分数分解为埃及分数# 不取巧也没有公式的硬做

分母分解成因子后 取其中的一些数 使它们的和等于分子即可

算因子和这里用例dfs回溯 特别注意要新传一个num_re = [i for i in nums] num_re.remove(x)

因为回溯很重要的是要还原 nums 不能对nums进行改动

while True:
    try:
        # 因子分解
        def div(n):
            out = [1]
            for i in range(2, int(n ** 0.5) + 1):
                if n % i == 0:
                    out.extend([i, n // i])
            return out

        # 数字合成
        def sum_div(nums, target, out):
            if target == 0:
                res.append(out)
                return True
            if target < 0 or sum(nums) < target:
                return False

            flag = False
            if nums:
                for x in nums:
                    num_re = [i for i in nums]
                    num_re.remove(x)
                    if sum_div(num_re, target - x, out + [x]):
                        flag = True
                        break

            return flag

        res = []

        x1, x2 = map(int, input().split("/"))

        i = 0
        while not res:
            i += 1
            divs = div(x2 * i)
            target = x1 * i
            if sum_div(divs, target, []):
                break

        out_res = ["1/" + str(x2 * i // d) for d in res[0]]
        print("+".join(out_res))
    except:
        break