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

#include <iostream>
#include <string>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

void egyptianFraction(ll nr, ll dr) {
    // 如果分子为0或分母为0，返回
    if (nr == 0 || dr == 0)
        return;
    
    // 如果分子能整除分母
    if (dr % nr == 0) {
        cout << "1/" << dr/nr;
        return;
    }
    
    // 如果分母能整除分子
    if (nr % dr == 0) {
        cout << nr/dr;
        return;
    }
    
    // 如果分子大于分母
    if (nr > dr) {
        cout << nr/dr << "+";
        egyptianFraction(nr%dr, dr);
        return;
    }
    
    // 找到第一个大于dr/nr的分母
    ll n = dr/nr + 1;
    cout << "1/" << n;
    
    // 计算新的分子和分母
    ll new_nr = nr * n - dr;
    ll new_dr = dr * n;
    
    // 化简分数
    ll g = gcd(abs(new_nr), new_dr);
    new_nr /= g;
    new_dr /= g;
    
    if (new_nr != 0) {
        cout << "+";
        egyptianFraction(new_nr, new_dr);
    }
}

int main() {
    string input;
    cin >> input;
    
    ll pos = input.find('/');
    ll nr = stoll(input.substr(0, pos));
    ll dr = stoll(input.substr(pos + 1));
    
    // 化简输入的分数
    ll g = gcd(nr, dr);
    nr /= g;
    dr /= g;
    
    egyptianFraction(nr, dr);
    cout << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public static void egyptianFraction(long nr, long dr) {
        if (nr == 0 || dr == 0)
            return;
            
        if (dr % nr == 0) {
            System.out.print("1/" + dr/nr);
            return;
        }
        
        if (nr % dr == 0) {
            System.out.print(nr/dr);
            return;
        }
        
        if (nr > dr) {
            System.out.print(nr/dr + "+");
            egyptianFraction(nr%dr, dr);
            return;
        }
        
        long n = dr/nr + 1;
        System.out.print("1/" + n);
        
        long new_nr = nr * n - dr;
        long new_dr = dr * n;
        
        long g = gcd(Math.abs(new_nr), new_dr);
        new_nr /= g;
        new_dr /= g;
        
        if (new_nr != 0) {
            System.out.print("+");
            egyptianFraction(new_nr, new_dr);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        
        String[] parts = input.split("/");
        long nr = Integer.parseInt(parts[0]);
        long dr = Integer.parseInt(parts[1]);
        
        long g = gcd(nr, dr);
        nr /= g;
        dr /= g;
        
        egyptianFraction(nr, dr);
        System.out.println();
    }
}

import math

def egyptian_fraction(nr, dr):
    if nr == 0 or dr == 0:
        return
        
    if dr % nr == 0:
        print(f"1/{dr//nr}", end="")
        return
        
    n = math.ceil(dr/nr)
    print(f"1/{n}", end="")
    
    new_nr = nr * n - dr
    new_dr = dr * n
    
    if new_nr != 0:
        print("+", end="")
        egyptian_fraction(new_nr, new_dr)

# 读取输入
fraction = input().strip()
nr, dr = map(int, fraction.split('/'))

# 计算并输出结果
egyptian_fraction(nr, dr)
print()  # 换行