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

import java.util.Objects;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String nextLine = in.nextLine();
            if (Objects.isNull(nextLine) || nextLine.equals("")) {
                break;
            }
            String[] split = nextLine.split("/");
            Integer n = Integer.parseInt(split[0]);
            Integer m = Integer.parseInt(split[1]);
            // 找出最大公约数
            Integer max = find(n, m);
            int a = n / max;
            int b = m / max;
            // 查找
            /* 以下是数学家斐波那契提出的一种求解埃及分数的贪心算法，准确的算法表述应该是这样的：
             * 设某个真分数的分子为a，分母为b;
             * 把b除以a的商部分加1后的值作为埃及分数的第一个分母c：1/c；
             * 将a乘以c再减去b，作为新的a；
             * 将b乘以c，得到新的b；
             * 如果a大于1且能被b整除，则最后一个分母为b/a；算法结束；
             * 或者，如果a等于1，则，最后一个分母为b；算法结束；
             * 否则重复上面的步骤。
             */
            StringBuilder sb = new StringBuilder();
            int c;
            while (a != 1) {
                //类似3/110的情况，这里加着方便快速得出结果
                //虽然没有这个if条件判断，也能得出，但是会慢很多，而且埃及分解结果不唯一，加了该判断结果会更快
                if (b % (a - 1) == 0) {
                    sb.append("1/")
                        .append(b / (a - 1))
                        .append('+');
                    a = 1;
                } else {
                    c = b / a + 1; //重要点
                    sb.append("1/")
                        .append(c)
                        .append('+');
                    a = a * c - b;      //  a/b-1/c=(a*c-b)/(b*c)，所以分子a = a * c - b;
                    b = c * b;          //  分母b = c * b;
                    if (b % a == 0) {
                        b = b / a;
                        a = 1;//直接跳出循环
                    }
                }
            }
            sb.append("1/")
                .append(b);
            System.out.println(sb.toString());
        }
    }

    public static Integer find(int n, int m) {
        int min = Math.min(n, m);
        int max = 1;
        for (int i = 1; i <= min; i++) {
            if (n % i == 0 && m % i == 0) {
                max = i;
            }
        }
        return max;
    }
}