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

解题思路：
1. 将分数拆分成分子和分母，模拟分数运算
1.1 化简分数 (只化简到分子为1的形式)
1.2 比较两个分数的大小
1.3 两个分数做差
2. 遍历因子（分子为1， 分母2~n）
2.1 对待分解的分数，减去因子，如果结果大于0，就记录该因子
2.2 如果结果==0，除了记录该因子，跳出循环
2.3 因子分母+1

class Solution:

    def _gcd(self, fz, fm):
        """ 化简分数 (只化简到分子为1的形式) """
        if int(fz % fm) == 0:
            return 1, fz//fm
        else:
            return fz, fm

    def _compare_fs(self, fz, fm, fz_2, fm_2):
        """ 比较两个分数的大小 """
        if fm == fm_2:
            return fz - fz_2
        if fz == fz_2:
            return fm_2 - fm
        return fz*fm_2 - fz_2*fm

    def _sub(self, fz, fm, fz_2, fm_2):
        """ 两个分数做差 """
        return self._gcd(fz * fm_2 - fz_2 * fm, fm*fm_2)

    def solve(self, fz, fm):
        rnt = list()
        start_fm = 2
        curr_fz, curr_fm = fz, fm
        while True:
            com_mp = self._compare_fs(curr_fz, curr_fm, 1, start_fm)

            if com_mp == 0:
                rnt.append(start_fm)
                break

            if com_mp > 0:
                rnt.append(start_fm)
                curr_fz, curr_fm = self._sub(curr_fz, curr_fm, 1, start_fm)
                if curr_fz == 1:
                    rnt.append(curr_fm)
                    break

            start_fm += 1

        rnt_str = ""
        for i in range(len(rnt)-1):
            rnt_str += "1/" + str(rnt[i]) + "+"
        rnt_str += "1/" + str(rnt[-1])

        return rnt_str



import sys
if __name__ == '__main__':
    is_IDE = False
    if is_IDE:
        fr = open("data/HJ82.txt", "r", encoding="utf-8")
    else:
        fr = sys.stdin

    while True:
        line = fr.readline().strip()
        if line == "":
            break
        line_list = line.split("/")
        print(Solution().solve(int(line_list[0]), int(line_list[1])))

    if is_IDE:
        fr.close()