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

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
type M = {div: number; sub: number}

rl.on('line', function (line) {
  const arr: M[] = []
  const _input = line.split('/').map(c => parseInt(c))
  const input: M = {div: _input[1], sub: _input[0]}
  const results = calc(input)
  const solutions = results.map(c => `${c.sub}/${c.div}`).join('+')
  console.log(solutions)
});

// 获取最大公约数
const gcd = (a: number, b: number): number => {
    if (b === 0) return a
    return gcd(b, a % b)
}

// 获取最小公倍数
const lcm = (a: number, b: number) => {
    return a * b / gcd(a, b)
}

const calc = (_input: M) => {
  let input = {..._input}
  const arr = []
  // 按数字从小到大遍历，并在公倍数放大到一致后再进行比较
  for(let i = 2; ; i++) {
    const target = {div: i, sub: 1}
    const [scaledTarget, scaledInput] = getScale(target, input)
    if (scaledTarget.sub === scaledInput.sub) {
      arr.push(target)
      break;
    } else if (scaledTarget.sub > scaledInput.sub) {
      continue
    } else {
      arr.push(target)
      input.div = scaledInput.div
      input.sub = scaledInput.sub - scaledTarget.sub
      if (input.sub === 1) {
        arr.push(input)
        break;
      }
    }
  }
  return arr
}

// 将两个不同分母大小的分数，缩放到统一的分母值
const getScale = (target: M, compareTo: M) => {
  const commonM = lcm(target.div, compareTo.div)
  const targetScaleSub = commonM / target.div * target.sub
  const compareToScaleSub = commonM / compareTo.div * compareTo.sub
  return [{div: commonM, sub: targetScaleSub}, {div: commonM, sub: compareToScaleSub}]
}