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

#include <iostream>
using namespace std;
long long gcd(long long a, long long b){
    //求a,b的最大公因数
    int r = a % b;
    while(r > 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
int main() {
    long long a = 0, b = 0;
    string s;
    cin>>s;
    for(int i = 0; i < s.length(); ++i){
        if(s[i] == '/'){
            for(int j = i + 1; j < s.length(); ++j){
                b = b * 10 + s[j] - '0';
            }
            break;
        }else a = a * 10 + s[i] - '0';
    }
    // cout<<b<<" "<<a<<endl;
    long long g = gcd(b, a);
    // cout<<g<<endl;
    a = a / g;
    b = b / g;
    if(a == 1)
        cout<<"1/"<<b;
    else {
        while(a != 1){
            // cout<<endl<<a<<" "<<b<<endl;
            long long q = b / a;
            cout<<"1/"<<q + 1;
            a = a * (q + 1) - b;
            b = b * (q + 1);
            g = gcd(a, b);
            a = a / g;
            b = b / g;
            cout<<"+";
        }
        cout<<"1/"<<b;
    }
}
// 64 位输出请用 printf("%lld")