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

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main() {
    string str;
    while (cin >> str) {
        int pos = str.find('/');
        long long a = stoi(str.substr(0, pos));
        long long b = stoi(str.substr(pos + 1));
        int g = gcd(a, b);
        if (g != 1) {
            a /= g;
            b /= g;
        }
        // a,b互质
        long long c;
        string ans;
        while (a > 1 && b % a != 0) {
            c = b / a + 1;
            ans += "1/" + to_string(c) + '+';
            a = a - b % a;
            b = b * c;
        }
        if (a > 1 && b % a == 0) {
            ans += "1/" + to_string(b / a);
        } else if (a == 1) {
            ans += "1/" + to_string(b);
        }
        cout << ans << endl;
    }
    return 0;
}