将真分数分解为埃及分数, 华为笔试题

分数为：a / b, a < b。
从1/2 , 1/3 ..., 1/ i , ... 1/ k 依次寻找。

如果1/i > a / b, 继续向后找。
如果1/i <= a / b, 添加 1 / i ， a / b - 1/ i 得到新的a,b, 如果此时a == 0, 结束。

import java.util.*;
public class Main {
    static long gcd(long a, long b) {
        if(a < b) return gcd(b, a);
        return b == 0 ? a : gcd(b, a%b);
    }
    static List<Integer> solution(long a, long b) {
        List<Integer> res = new ArrayList<>();
        for(long i=2; true ; i++) {
            long gc = gcd(a, b);
            a = a / gc; b = b / gc;
            if(a == 1) {
                res.add((int)b); break;
            }
            long y = i*b / gcd(i, b);
            if(y / i > y/b*a) continue;
            long x = y/b*a - y / i;
            res.add((int)i);
            a = x; b = y;
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String[] s = sc.next().split("/");
            int a = Integer.valueOf(s[0]), b = Integer.valueOf(s[1]);
            List<Integer> res = solution((long)a, (long)b);
            for(int i=0; i < res.size()-1; i++) {
                System.out.print("1/"+res.get(i) + "+");
            }
            System.out.println("1/"+res.get(res.size()-1));
        }

    }
}