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

实际用时在260ms左右，解法相对简单

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    while ((line = await readline())) {
        let [z, m] = line.split("/");

        let arr = [];
        

        // 解法四：优化后的解法三 // 前面三个不好的解法就不放出来了
        function add3(i) {
			// 首先判断  m/(z-1) 如果可以除通，则直接解决，如   3/24 + 1/24
            if (m % (z - 1) == 0) {
                arr.push(m / (z - 1), m);
                return 1;
            }
			// 最后如果上述情况都不行的话，就
            // 先判断是  1/i 是否小于当前的 z/m
            // 如果小于，则求最小公倍数，并减去  1/i 再继续计算
            if(m<i*z){
                let bei = beishu(i, m);
                let newZ = (bei / m) * z - bei / i; // 新的分子
                
                if (newZ == 1) {
                    arr.push(i, bei);
                    return 1;
                }
                if (newZ > 1) {
                    arr.push(i);
                    if (bei % newZ == 0) {
                        arr.push(bei / newZ);
                        return 1;
                    }
                    if (bei % (newZ - 1) == 0) {
                        arr.push(bei / (newZ - 1), bei);
                        return 1;
                    }
                    m = bei;
                    z = newZ;
                    // return add2(i + 1, bei, newZ);
                }
            }
            return 2;
        }
        for (let i = 2; i < 999999999; i++) {
            if (add3(i) == 1) {
                i = 999999999;
            }
        }
        console.log(
            arr
                .map((v) => {
                    return "1/" + v;
                })
                .join("+")
        );

        // 求最小公倍数
        function beishu(a, b) {
            let [max, min] = [a > b ? a : b, a < b ? a : b];
            if (max % min == 0) return max; // 是其中一个倍数的时候，则返回那个大的值，就是最小公倍数，否则往下找
            let arr = []; // 公约数
            for (let i = 2; i < max * min; i++) {
                if (max % i == 0 && min % i == 0) {
                    arr.push(i);
                    max = max / i;
                    min = min / i;
                }
            }
            arr.push(max * min);
            return arr.reduce((pre, v) => (pre *= v), 1);
        }
        // console.log(beishu(+z,+m))
    }
})();