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

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

typedef long long LL;//分母可能很大，乘法后可能会爆int
const int N = 1010;
LL ans[N];//记录埃及分数的分母
LL a, b;
int cnt;//ans数组的大小
//欧几里得
LL gcd(LL x, LL y) {
    return y == 0 ? x : gcd(y, x % y);
}

void find(LL a, LL b) {
    //递归终点
    if (a == 1) {
        ans[cnt++] = b;
        return ;
    }
    //寻找下一次求解的目标
    LL c = b / a + 1;
    ans[cnt++] = c;
    a = a - b % a;
    b = b * c;
    //最简形式递归求解
    LL t = gcd(a, b);
    find(a / t, b / t);
}

int main() {
    string s;
    while (cin >> s) {
        int i = 0;
        for(; i < s.size(); i++) if (s[i] == '/') break;
        a = 1ll * stoi(s.substr(0, i));
        b = 1ll * stoi(s.substr(i+1));
        find(a, b);
        for (int i = 0; i < cnt; ++i) {
            cout << "1/" << ans[i];
            if (i < cnt-1) cout << "+";
        }
        cout << endl;
        cnt=0;
    }
    return 0;
}

递归 果然有些困难啊