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

#include <cstdio>
#include <iostream>
using namespace std;
//没思路，穷举，但是分子分母用32位有符号会溢出
struct Item {
    uint64_t a;
    uint64_t b;
    void Sub(const Item& r) {
        auto u = a * r.b - b * r.a;
        auto d = b * r.b;
        a = u;
        b = d;
    }
    bool IsZero() {
        return a == 0;
    }
    bool operator >=(const Item& r) {
        return a * r.b >= b * r.a;
    }
    string ToString() {
        return to_string(a) + "/" + to_string(b);
    }
};

int main() {
    uint64_t a, b;
    scanf("%lu/%lu", &a, &b);
    Item in{a,b};
    Item t{1,2};
    auto first = true;
    while(true) {
        if(in >= t) {
            if(!first) {
                cout << "+";
            }
            first = false;
            cout << t.ToString();
            in.Sub(t);
            if(in.a == 1) {
                cout << "+" << in.ToString();
                break;
            }
            if(in.IsZero()) {
                break;
            }
        }
        t.b++;
    }
}
// 64 位输出请用 printf("%lld")