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

真分数的问题首先想到的肯定是 1/2+1/3+...+1/(∞-1)+1/∞==1， 所以比1/2大就减掉，小就往后走；剩下的比1/3大，再减，小继续往后；以此类推；（递归部分） 然后发现这样虽然可以搞定，但是太慢（根据提交结果看，时间消耗属于最后的3%那一部分，资源消耗也在最后的20%）， 并且发现和给定的结果不一样 ps:8/11 我们给出的结果是 1/2+1/5+1/37+1/4070; 明显我们的结果太消耗算力，分析结果的 3/110 = 1/55 + 1/110; 可以推出这种方式z/m解为 1/m + (z-1)/m; 这样就不用大量计算了，只需要 m%(z-1) == 0 即可 当然这里可以考虑系统给的一些不用算的，m%z==0 的直接转换 1/(m/z) 在

var arr = [];
for(var i = 0;i<100;i++){
    var str = readline();
    if(str){
        arr[i] = str;
    }else{
        i = 100;
    }
}
for(var i = 0;i<arr.length;i++){
    var arr1 = [];
//     console.log(arr[i]);
    arr1 = arr[i].split("\/");
    print(getOne(arr1));
}

function getOne(arr){
    var z = 1*arr[0];//分子
    var m = 1*arr[1];//分母 m>z
    var arrM = [];//埃及分数分母的集合数组
    getAJ(z,m,arrM);
    var str = "1/";
    var result = "";
    for(var i = 0;i<arrM.length;i++){
        if(arrM.length == i + 1){
            result = result + str + arrM[i];
        }else{
            result = result + str + arrM[i] + "+" 
        }
    }
    return result;
}


function getAJ(z,m,arrM,x){//z 分子 m 分母 arrM 埃及分母的集合的数组 分母起点，初始默认为2
    if(z!=0 && m%z == 0){
        arrM.push(m/z);
        return arrM;
    }
    x = x || 2;//初始分母从2开始
    if(z == 1){
        arrM.push(m);
        return arrM;
    }else if(z == 0){
        return arrM;
    }else if(m%(z-1)==0){
        arrM.push(m/(z-1));
        arrM.push(m);
        return arrM;
    }
    /**递归部分*/
    for(var i = x;i<999999999;i++){
        if(z*i>=m){
            arrM.push(i);
            getAJ(z*i-m,m*i,arrM,i+1);
            i = 999999999;
        }
    }
}