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

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//辗转法
void Egypt(int a,int b,vector<int> &_rs)
{
    while(a!=1)
    {
        //先约分
        int gcd=__gcd(a,b);
        a=a/gcd;
        b=b/gcd;
        int q=b/a;
        _rs.push_back(1+q);
        a=a-b%a;
        b=b*(1+q);
    }
    _rs.push_back(b);
}

int main()
{
    int a=0,b=0;
    char ch='/';
    while(cin>>a>>ch>>b)
    {
        vector<int> rs;
        Egypt(a,b,rs);
        for(int i=0;i<rs.size()-1;++i)
        {
            printf("1/%d+",rs[i]);
        }
        printf("1/%d\n",rs.back());
    }
    return 0;
}