题目的主要信息：

• 分子为1的分数称为埃及分数
• 输入一个分子比分母小的分数，请分解为分母不同的埃及分数
• 分子和分母有可能gcd不为1
• 如有多个解，输出一个即可

方法一：迭代

具体做法：

如下图公式推算，我们可以贪心地用这种除法取余地方式更新分子分母，不断获取分子为1的分数。

因为分子分母gcd可能不为1，因此，如果分母可以整除分子，可以直接输出约分后的结果，跳出循环。

#include<iostream>
#include<string>
using namespace std;

int main(){
    int a, b; //分别是分子分母
    char op; //除号
    while(cin >> a >> op >> b){
        while(a != 1){ //直到最后的a为1
            if(b % a == 0){ //先去掉公因子
                b = b / a;
                break;
            }
            //按照公式推算运算
            int x = b / a;
            int y = b % a;
            cout << 1 << op << x + 1 << "+";
            a -= y;
            b *= x + 1;
        }
        cout << 1 << op << b << endl;
    }
}

复杂度分析：

• 时间复杂度：$O(a)O(a)$，最坏情况下余数都为1，要迭代$aa$次
• 空间复杂度：$O(1)O(1)$，常数空间

方法二：递归

具体做法：

上述迭代的方式也可以用递归来实现，只需要把更新后的分子分母送入递归函数即可。

递归的出口有两个：一个是分子为1，可以直接输出，出递归；一个是分母可以整除分子，也可以直接输出然后出递归。

我们再加一个优化，因为当$b\mathrm{\%}(a-1)=0b\; \backslash \%\; (a-1)\; =\; 0$时，有$a\mathrm{/}b=1\mathrm{/}(b\mathrm{/}(a-1))+1\mathrm{/}ba/b=1/(b/(a-1))\; +\; 1/\; b$，可以直接分解成两个，省去了上述一些继续分解的步骤，可以优化一些时间。

#include<iostream>
#include<string>
using namespace std;

void recursion(int a, int b){
    if(a == 1){
        cout << 1 << "/" << b << endl;
        return;
    }
    if(b % a == 0){ //去掉公因子
        recursion(1, b / a);
        return;
    }
    if(b % (a - 1) == 0){ //整除a-1的情况
        cout << 1 << "/" << b / (a - 1) << "+";
        recursion(1, b);
        return;
    }
    cout << 1 << "/" << b / a + 1 << "+";
    recursion(a - b % a, b * (b / a + 1)); //根据公式更新分子分母送入递归
}

int main(){
    int a, b; //分别是分子分母
    char op; //除号
    while(cin >> a >> op >> b){
       recursion(a, b);
    }
}

复杂度分析：

• 时间复杂度：$O(a)O(a)$，最坏情况下要递归$aa$次
• 空间复杂度：$O(a)O(a)$，递归栈空间最深为$aa$