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

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        String[] parts = input.split("/");
        int a = Integer.parseInt(parts[0]);
        int b = Integer.parseInt(parts[1]);

        // 约分
        int gcd = gcd(a, b);
        a /= gcd;
        b /= gcd;

        List<Long> denominators = new ArrayList<>();

        long currentA = a;
        long currentB = b;

        while (currentA > 0) {
            if (currentA == 1) {
                denominators.add(currentB);
                break;
            }
            long k = (currentB + currentA - 1) / currentA; // 向上取整
            denominators.add(k);

            long newA = currentA * k - currentB;
            long newB = currentB * k;

            // 约分新的分子和分母
            long newGcd = gcd(newA, newB);
            if (newGcd > 1) {
                newA /= newGcd;
                newB /= newGcd;
            }

            currentA = newA;
            currentB = newB;
        }

        // 构建输出字符串
        StringBuilder result = new StringBuilder();
        for (long d : denominators) {
            result.append("1/").append(d).append("+");
        }
        if (result.length() > 0) {
            result.setLength(result.length() - 1); // 移除最后一个加号
        }
        System.out.println(result);
    }

    // 计算最大公约数，处理int类型约分
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 处理long类型的最大公约数
    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理与约分：首先将输入的分数分割为分子和分母，并约分为最简形式。
2. 长整型处理：使用long类型变量currentA和currentB来存储当前的分子和分母，避免大数相乘时溢出。
3. 贪心分解：每次选择最大的埃及分数，计算剩余部分，并更新当前的分子和分母。使用长整型运算确保准确性。
4. 约分处理：在每一步分解后，对新的分子和分母进行约分，确保后续计算的正确性。
5. 结果输出：收集所有埃及分数的分母，并按指定格式输出。