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

/**/
#include <iostream>
using namespace std;
//基本思路是不断找小于等于a/b的最大埃及整数（保证分母从2开始递增），并作差,差值再寻找小于等于差值的最大埃及整数，直到等于0
//由调和数列和为无穷的性质，该方法应该能将任意大于0的整数分解为有限个埃及整数的和
//运行结果最后一项不对，不知道为什么（现在知道了，int改成long int）
int main() {
    long int i,j;
    scanf("%ld/%ld",&i,&j);
    long int k=j/i;;
    while(i){
        while(i*k-j<0){
            k++;
        }
        if(i*k-j>0){
            cout<<1<<"/"<<k<<"+";
            i=i*k-j;
            j=j*k;
            //例子过大时，无效循环太多，这里逃过绝大部分无效循环
            k=j/i;
        }
        else if(i*k-j==0){
            cout<<1<<"/"<<k;
            break;
        }
    }
}

// 64 位输出请用 printf("%lld")