首页 > 试题广场 >

将真分数分解为埃及分数

[编程题]将真分数分解为埃及分数
  • 热度指数:84318 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
\hspace{15pt}定义分子为 1 的分数为埃及分数,例如 \tfrac{1}{2}, \tfrac{1}{100} 等。
\hspace{15pt}现在,对于给定的一个分子小于分母的分数 \tfrac{a}{b},请将其分解为若干个不同的埃及分数之和。随后,使用 \texttt{1/} b_1 \texttt{+1/} b_2 \texttt{+} \cdots \texttt{+1/} b_n 的格式输出结果,其中,b_1,b_2,\dots,b_n 表示每一个埃及分数的分母。

输入描述:
\hspace{15pt}a \texttt{/} b 的格式输入一个分数 \tfrac{a}{b},其中 1 \leqq a < b \leqq 100。不保证分数为最简分数。


输出描述:
\hspace{15pt}\texttt{1/} b_1 \texttt{+1/} b_2 \texttt{+} \cdots \texttt{+1/} b_n 的格式输出结果,其中,b_1,b_2,\dots,b_n 表示每一个埃及分数的分母。

\hspace{15pt}如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

2/4

输出

1/2

说明

\hspace{15pt}在这个样例中,输出 \texttt{1/3+1/6} 也是正确的。
示例2

输入

8/11

输出

1/2+1/5+1/55+1/110
这确实是解,但是分裂到最后,数字越来越大,得用BigInteger来装了
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { // 注意 while 处理多个 case
            String line = in.nextLine();
            int a = Integer.parseInt(line.split("/")[0]);
            int b = Integer.parseInt(line.split("/")[1]);
            //先分子分母化简,用辗转相除法
            int bigCase = getBigCase(a, b);
            a = a / bigCase;
            b = b / bigCase;
            //a/b = a个1/b求和. 但是题意要求每个1/x都不同,所以只能保留第一个1/b,剩下的需要裂变
            //裂变的方案有很多种.例如: 1/b = 1/2b + 1/3b + 1/6b, 1/b = 1/2b + 1/4b + 1/8b + 1/12b + 1/24b
            //最简单的应该是: 1/b = 1/(b+1) + 1/b(b+1)
            // 所以答案出来了,先将a/b分裂成a个1/b,然后每发现一次重复数据,就分裂成2个,直到没有重复为止.
            //为了简化,list存分母即可
            List<Long> list = new ArrayList<Long>();
            for (int i = 0; i < a; i++) {
                add(list, b);
            }
            StringBuilder sb = new StringBuilder();
            for (long d : list) {
                sb.append("1/" + d + "+");
            }
            System.out.println(sb.substring(0, sb.length() - 1));
        }
    }

//取最大公约数. 务必保证a<b
    static int getBigCase(int a, int b) {
        while (a != 0) {
            int t = b % a;
            b = a;
            a = t;
        }
        return b;
    }

    static void add(List<Long> list, long b) {
        if (list.contains(b)) {
            //如果已经有了,就分裂成2个分别添加
            add(list, b + 1);
            add(list, b * (b + 1));
        } else {
            list.add(b);
        }
    }
}


发表于 2025-06-05 20:44:24 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] a = in.nextLine().split("/");
        StringBuilder out = new StringBuilder();
        int b = Integer.parseInt(a[0]);
        int c = Integer.parseInt(a[1]);
        int d = gcd(b, c);
        if (b % d == 0 && c % d == 0) {
            b = b / d;
            c = c / d;
        }
        // 注意 hasNext 和 hasNextLine 的区别
        //  比如8/11 先K=ceil(11/8)  1/K K=2
        findk(b, c, out);
        System.out.println(out);
    }
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    private static  int findk(int a, int b, StringBuilder e) { //a分子 b分母
        int K = (int)Math.ceil((double)b / (double)a);
        //System.out.println(K+"KKKKKK");
        e.append(1 + "/" + K + "+");
        int c = a * K - b;
        int d = b * K;
        int f = gcd(c, d);
        if (c % f == 0 && d % f == 0) {
            c = c / f;
            d = d / f;
        }//约分后 分子为1  c=2 d=693   8/2772 2/693
        if (c != 1&&c!=2) {
            if (d % (c - 1) == 0 && c != 1) {
                e.append(1 + "/" + d / (c - 1) + "+" + 1 + "/" + d);
                return 0;
            }
        }
        if(c==1){
            e.append(c + "/" + d);
            return 0;
        }//2/693

        return findk(c, d, e);
    }
}
发表于 2025-03-21 11:59:20 回复(0)
最原始的思路就是逐级切割,就像一块蛋糕,我们将自己需要的最大的一部分按要求切下来,然后对剩下的一部分将进行同样的操作,直至终止条件的出现并终止。但是由于数据长度的限制,对于一些过大的特殊数值会超出并报错。这个好解决,不过就是在加一个特殊情况的判定。有兴趣的可以写一个有限情况的特殊判定方法过一些有限的示例。
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       String s=sc.next();
       String[] num=s.split("/");
       int a=Integer.parseInt(num[0]);
       int b=Integer.parseInt(num[1]);
        dijian(2,a,b);
        

    }
    //执行切割直至到终止条件出现
    private static void dijian(long c,long a,long b){
        long fenzi1=a*c;
        long fenzi2=b;
        if(fenzi1>fenzi2){
            System.out.print(1+"/"+c+"+");
            long[] zm=Huajian(a*c-b,b*c,2);
            //为了过最后一个示例写的特殊情况处理
            //有兴趣的话可以写一个有限情况的处理方法,然后在这里调用
            //举个例子,如果要过8/11的话,把这里的判断条件改成(zm[0]==3&&zm[1]%2==0),然后输出:1/zm[1]/2+1/zm[1]就行了
            if(zm[0]==4&&zm[1]%3==0){
                System.out.print(1+"/"+zm[1]/3+"+"+1+"/"+zm[1]);
            }else{
                dijian(c+1,zm[0],zm[1]);
            }
            
        }else if(fenzi1==fenzi2){
            System.out.print(1+"/"+c);
        }else{
            dijian(c+1,a,b);
        }
    }
    //将分子分母化简到最简分数形式
    private static long[] Huajian(long a,long b,long k){
        long[] hj=new long[2];
        hj[0]=a;
        hj[1]=b;
       if(a%k==0&&b%k==0){
        hj[0]=hj[0]/k;
        hj[1]=hj[1]/k;
        return Huajian(hj[0],hj[1],k);
       } 
        if(k>=a){
        return hj;
       }else{
        return Huajian(a,b,k+1);
       }
      
        
    }
}


发表于 2025-02-24 19:43:29 回复(0)
用数学的方法解决这道题:将分子分母同时乘以一个数(这个数从一开始)得到一个新分数,求新分数里分母的所有除本身因数用来做分子,再求这些因数所有可能的组合的和,如果等于新分数的分子,得出结果。比如题目中的8/11,分子分母同乘6,得到48/66,求得66的所有除本身因数(1,2,3,6,11,12,33),求所有因数组合的和,发现1+3+11+33的和为48,所以结果为1/66,3/66,11/66,33/66,即1/2+1/6+1/22+1/66。
import java.math.*;
import java.util.*;


class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String aaa = in.nextLine();
        String[] aa = aaa.split("/");
        int a = Integer.parseInt(aa[0]);
        int b = Integer.parseInt(aa[1]);
        if(b%a == 0){
            System.out.println(1+ "/" + b/a);
        } else if (a==1) {
            System.out.println(a+ "/" + b);
        } else {
            List<Integer> result = new ArrayList<>();
            boolean p = false;
            int d = 0;
            for(int i = 1;i<b;i++){
                int c = a * i;
                d = b * i;
                int[] yinshu = new int[d];
                int e = 0;
                int length = 0;
                for(int j = 1;j<d;j++){
                    if(d%j==0){
                        yinshu[e] = j;
                        e++;
                        length = length*10 + 1;
                    }
                }

                String length1 = Integer.toString(length);
                int length2 = Integer.parseInt(length1,2);
                for(int j = 0;j<=length2;j++){
                    String x = Integer.toBinaryString(j);
                    x = String.format("%" + length1.length() +"s" , x);
                    x = x.replace(' ','0');
                    int r = 0;
                    for(int jj = 0;jj<x.length();jj++){
                        if(x.charAt(jj) == '1'){
                            r+=yinshu[jj];
                        }
                    }
                    if(r==c){
                        p = true;
                        for(int jj = 0;jj<x.length();jj++){
                            if(x.charAt(jj) == '1'){
                                result.add(yinshu[jj]);
                            }
                        }
                        break;
                    }
                }
                if(p){
                    break;
                }
            }
            //System.out.println("fengmu:" + d);
            for (int i = result.size() -1 ;i>0;i--) {
                System.out.print(1+ "/" + d/result.get(i) + "+");
            }
            System.out.print(1+ "/" + d/result.get(0));
        }
    }
}




发表于 2025-02-19 11:05:17 回复(0)
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static String res = "";
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
List<Float> list = new ArrayList<>();

while (in.hasNextLine()) { // 注意 while 处理多个 case
String a = in.nextLine();
String aas[] = a.split("/");
int[] aa = new int[] {Integer.valueOf(aas[0]), Integer.valueOf(aas[1])};
if (aa[1] % aa[0] == 0) {
System.out.println(1 + "/" + aa[1] / aa[0]);
continue;
}
get(aa);
System.out.println();
}
}
public static void get(int[] aa) {
List<Integer> list = getCombo(aa[1]);
if (list.size() > 1) {
if (getMatches(aa[0], list, 0, 0, "")) {
String[] ss = res.split("_");
// System.out.println(res);
for (int i = 0; i < ss.length; i++) {
System.out.print(1 + "/" + aa[1] / Integer.valueOf(ss[i]));
if (i != ss.length - 1)System.out.print("+");
}
return;
}
}
int j = 2;
while (true) {
List<Integer> list2 = getCombo(aa[1] * j);
if (getMatches(aa[0] * j, list2, 0, 0, "")) {
String[] ss = res.split("_");
for (int i = 0; i < ss.length; i++) {
System.out.print(1 + "/" + aa[1] * j / Integer.valueOf(ss[i]));
if (i != ss.length - 1)System.out.print("+");
}
return;
}
j++;
}
}
public static boolean getMatches(int a, List<Integer> list, int i, int sum,
String s) {
if (sum == a) {
res = s.substring(1);
return true;
} else if (i == list.size()) {
return false;
} else {
return getMatches(a, list, i + 1, sum + list.get(i), s + "_" + list.get(i)) ||
getMatches(a, list, i + 1, sum, s);
}

}
public static List<Integer> getCombo(int i) {
List<Integer> list = new ArrayList<>();
int half = i / 2;
int j = 1;
while (j <= half) {
if (i % j == 0) {
list.add(j);
}
j++;
}
return list;
}
}
发表于 2024-09-14 23:15:16 回复(0)
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static class Fraction {
        public double deno; //分母
        public double nume; //分子
        public Fraction(double nume, double deno) {
            this.nume = nume;
            this.deno = deno;
        }
        public Fraction(String FraStr) {
            this(Double.valueOf(FraStr.split("/")[0]).doubleValue(),
                 Double.valueOf(FraStr.split("/")[1]).doubleValue());
        }
        @Override
        public String toString() {
            return String.format("%.0f/%.0f", nume, deno);
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            Fraction proper = new Fraction(in.next());
            //对这个真分数
            //遍历自然数2,3,4,......
            //当找到一个自然数x,满足 1/x <= proper时
            //proper -= 1/x
            //将1/x 添加到Egyption
            //遍历自然数x+1, x+2, x+3, ......
            //重复上述步骤直到proper == 0
            //其中分数的运算和比较还需要通分和化简,此处省略未表
            List<Fraction> retList = new ArrayList<>();
            double x = 2.0;
            while (proper.nume != 0) {
                while (!isLowerThanPrev(new Fraction(1.0, x), proper)) {
                    x ++;
                }
                Fraction frac = new Fraction(1, x);
                reduction(frac, proper);
                proper.nume -= frac.nume;
                simplify(frac);
                retList.add(frac);
                if (proper.nume == 1) {
                    retList.add(new Fraction(1, proper.deno));
                    proper.nume = 0;
                }
            }
            String retStr = String.join("+",retList.stream().map(frac -> frac.toString()).collect(Collectors.toCollection(ArrayList<String>::new)));
            System.out.println(retStr);
        }
    }
    public static boolean isLowerThanPrev(Fraction current, Fraction proper) {
        reduction(current, proper);
        return current.nume <= proper.nume;
    }
    public static void reduction(Fraction frac1, Fraction frac2) {   //通分
        // simplify(frac1);
        simplify(frac2);
        double deno1 = frac1.deno;
        double deno2 = frac2.deno;
        double deno_ = lcm(Math.max(deno1, deno2), Math.min(deno1,
                           deno2)); //求得通分的分母
        frac1.deno = deno_;
        frac2.deno = deno_;
        frac1.nume *= deno_ / deno1;
        frac2.nume *= deno_ / deno2;
    }
    public static void simplify(Fraction frac) {   //化简
        double nume_ = frac.nume;
        double deno_ = frac.deno;
        double gcd_ = gcd(deno_, nume_);
        frac.nume = nume_ / gcd_;
        frac.deno = deno_ / gcd_;
    }
    public static double lcm (double a, double b) { //求最小公倍数
        double r = a * b / gcd(a, b);
        return r;//当a*b的积很大时,有越界风险
    }
    public static double gcd (double m, double n) { //求最大公因数
        double t = m % n;
        while (t != 0) {
            m = n;
            n = t;
            t = m % n;
        }
        return n;
    }
}

发表于 2024-06-01 23:28:35 回复(0)
基本思想就是贪心算法,找到离当前真分数x/y最近的埃及分数 1/(y/x+1),用当前真分数x/y减去找到的这个埃及分数1/(y/x+1),对得到的结果依次重复上述操作,如果得到的结果为埃及分数或化简之后为埃及分数,则结束。引入一个类,同核心代码只有几行:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String inputString = in.nextLine();
String temp[] = inputString.split("/");
long up = Long.valueOf(temp[0]);
long down = Long.valueOf(temp[1]);
Fenshu fenshu = new Fenshu(up, down);
List<String> list = new ArrayList<String>();
while (fenshu.up != 1) {
Fenshu toMinus = findTheMaxToMinus(fenshu);
list.add(toMinus.toString());
fenshu = fenshu.minus(toMinus);
if (fenshu.down % fenshu.up == 0) {
fenshu = new Fenshu(1, fenshu.down / fenshu.up);
}
}
list.add(fenshu.toString());
System.out.println(String.join("+", list));
}
in.close();
}

public static Fenshu findTheMaxToMinus(Fenshu fenshu) {
long n = fenshu.down / fenshu.up + 1;
return new Fenshu(1, n);
}
}

class Fenshu {
// 分子
long up;
// 分母
long down;

public Fenshu minus(Fenshu fenshu) {
long newDown = down * fenshu.down;
long newUp = up * fenshu.down - fenshu.up * down;
return new Fenshu(newUp, newDown);
}

public Fenshu(long up, long down) {
this.up = up;
this.down = down;
}

@Override
public String toString() {
return up + "/" + down;
}
}

发表于 2023-11-19 16:51:27 回复(0)
1/n = 1/(n+1) + 1/n(n+1),https://baike.baidu.com/item/%E5%9F%83%E5%8F%8A%E5%88%86%E6%95%B0/634864,埃及分数可以不断地演化成其他多个埃及分数之和,按原题意,是有无数多个符合调节的输出的。如果要求结果中各埃及分数的分母取最小值,也就是 1/n 不化解成 1/(n+1) + 1/n(n+1),那么本题解输出就只有一种。


发表于 2023-08-11 10:35:29 回复(0)
比较a/b与1/i的值 大于就输出并计算新的a/b,小于就i++;直到分子为0;也就是a=0为止
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static boolean compare(int m,int n,int q)
    {
          if(q*m>=n)
          {
            return true;
          }
          else
          {
            return false;
          }
    }
            public static ArrayList<Integer> play(int m,int n,int q)
          {
            ArrayList<Integer> num=new ArrayList<>();
             int k=q*m-n;   //分子
             int p=q*n;     //分母
             num.add(k);
             num.add(p);
            return num;
                     
          }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayList<String> num=new ArrayList<>();
        while (in.hasNext())
        {
            String a = in.next();
            num.add(a);
        }
        for(String p:num)
        {
            ArrayList<String> result=new ArrayList<>();   //存放结果
            int x=0;
            for(int i=0;i<p.length();i++)
            {
                if(p.charAt(i)=='/')
                {
                          x=i;
                          break;
                }
            }
            String b="";
             for(int i=0;i<x;i++)
            {
                    b=b+p.charAt(i);
            }
            int m=Integer.parseInt(b);  //分子
            String k="";
            for(int i=x+1;i<p.length();i++)
            {
                    k=k+p.charAt(i);
            }
            int n=Integer.parseInt(k);   //分母

             int q=2;  //分母初始化
             while(m!=0)
             {
                if(compare(m,n,q)==true)   //比较m/n和 1/q的大小
                {
                     
                     ArrayList<Integer> and=new ArrayList<>();
                     and=play(m,n,q);
                     m=and.get(0);
                     if(m!=0)
                     {
                        result.add("1/"+q+"+");
                     }
                     else
                     {
                        result.add("1/"+q);
                     }
                     n=and.get(1);
                }
                q++;
             }
       
        String end="";
        for(String g:result)
        {
            end=end+g;
        }
       System.out.println(end);

        }
    }
}
发表于 2023-04-30 17:05:39 回复(0)
哈哈哈,题目有问题
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
            String[] input = in.nextLine().split("/");
            for (int i = 0;i < Integer.valueOf(input[0]);i ++){
                System.out.print("1/"+input[1]);
                if (i != Integer.valueOf(input[0])-1){
                    System.out.print("+");
                }
            }
            System.out.println();
    }
}

发表于 2023-03-26 22:36:21 回复(1)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String[] frac = in.next().split("/");
            long a = Long.parseLong(frac[0]), b = Long.parseLong(frac[1]);
            for (long c = 0; b % a != 0; a -= b % a, b *= c) {
                c = b / a + 1;
                System.out.print("1/" + c + "+");
            }
            System.out.println("1/" + b / a);
        }
    }
}

发表于 2023-03-12 19:04:57 回复(0)
看了埃及分数的百度百科,不明觉厉。


参照百度百科最后面的Pascal代码,有如下Java代码。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String[] str = in.nextLine().split("\\/");
            long a = Integer.valueOf(str[0]);
            long b = Integer.valueOf(str[1]);
            long c = 0;
            String res = "";
            for ( ; a != 1 && b % a != 0 ;) {
                c = b / a + 1;
                a = a * c - b;
                b = b * c;
                res += ("1/" + c + "+");
            }
            if (b % a == 0 && a != 1) {
                res += ("1/" + b / a);
            } else if (a == 1) {
                res += ("1/" + b);
            }
            System.out.println(res);
        }
    }
}


发表于 2023-02-24 13:00:20 回复(0)
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 str = in.nextLine();
            // 获得输入分子
            long a = Integer.parseInt(str.split("/")[0]);
            // 获得输入分母
            long b = Integer.parseInt(str.split("/")[1]);
            long c = 0;
            // 定义StringBuffer用于拼接字符串
            StringBuffer newStr = new StringBuffer();
            /**
            数学家斐波那契提出的一种求解埃及数的贪心算法,准确的算法表述应该是这样的:
            设某个真分数的分子为a,分母为b;
            把c=(b/a+1)作为分解式中第一个埃及数的分母;
            将a-b%a作为新的a;
            将b*c作为新的b;
            如果a等于1,则最后一个埃及数为1/b,算法结束;
            如果a大于1但是a能整除b,则最后一个埃及数为1/(b/a),算法结束;
            否则重复上面的步骤。
             */
            while (true) {
                c = b / a + 1;
                a = a - b % a;
                b = b * c;
                newStr.append("1/" + String.valueOf(c) + "+");
                if (a == 1) {
                    newStr.append("1/" + String.valueOf(b));
                    break;
                }
                if (a > 1 && b % a == 0) {
                    newStr.append("1/" + String.valueOf(b / a));
                    break;
                }
            }
            // 输出结果
            System.out.println(newStr.toString());
        }
    }
}

发表于 2023-02-14 15:35:14 回复(1)
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 s = in.nextLine();
            String[] parts=s.split("/");
            long a=Integer.parseInt(parts[0]);
            long b=Integer.parseInt(parts[1]);
            String result="";
            long c=0;
            while(b%a!=0){
               c=b/a+1;
               result=result+"1/"+c+"+";
               a=a*c-b;
               b=b*c;
            }
            result=result+"1/"+b/a;
            System.out.println(result);
        }
    }
}

发表于 2023-02-06 14:33:55 回复(1)
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            List<Integer> list = getEgyptDeno(in.nextLine());
            int i = 0, len = list.size();
            StringBuffer sb = new StringBuffer();
            for (i = 0; i < len; i++) {
                sb.append("1/").append(list.get(i));
                if (i < len - 1) {
                    sb.append("+");
                }
            }
            System.out.println(sb.toString());
        }
    }

    public static List<Integer> getEgyptDeno(String str) {
        String[] arr = str.split("/");
        int a = Integer.parseInt(arr[0]), b = Integer.parseInt(arr[1]), c = 0;
        List<Integer> resList = new ArrayList<>();
        while (a != 1 && b % a != 0) {
            if (b % (a - 1) == 0) {
                resList.add(b / (a - 1));
                a = 1;
            } else {
                c = b / a + 1;
                resList.add(c);
                a = a * c - b;
                b = b * c;
            }
        }
        if (a == 1) {
            resList.add(b);
        } else if (b % a == 0) {
            resList.add(b / a);
        }
        return resList;
    }
}

发表于 2023-01-30 21:49:32 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String[] s = in.next().split("/");
            int fz = Integer.parseInt(s[0]);
            StringBuilder sb = new StringBuilder();
            while(fz-->0)
                sb.append("1/"+s[1]+"+");
            System.out.println(sb.deleteCharAt(sb.length()-1).toString());
        }
    }
}

发表于 2022-10-04 21:08:22 回复(2)
//这都行
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String next = sc.next();
        String[] split = next.split("/");
        String time = split[0];
        String m = split[1];
        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < Integer.valueOf(time); i++) {
            list.add("1/"+m);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
            sb.append("+");
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }

}


发表于 2022-08-21 15:40:01 回复(1)
耶,为啥最后一个用例我没通过:
//package OnlineTest.normal;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        /*把一个真分数写成多个不相同的分子为1的分数之和*/
        /*贪心算法:每次找最大的分子为1的数
        * a/b=a/(ak+c)=1/(k+c/a),令a>c,即可得到a/b>1/(1+k);
        * */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nums = br.readLine().split("\\/");
        int[] num = new int[nums.length];
        int top, bottom,k,c;
        top = num[0] = Integer.valueOf(nums[0]);
        bottom = num[1] = Integer.valueOf(nums[1]);
        double sum = 0;
        k = 0;
        while (top!=1) {
            k = (int) bottom / top;
            c = bottom % top;
            int rr = 1 + k;
            System.out.printf("1/%d+", rr);
            sum += (double) 1 / (1 + k);
            int[] r = coM(top, bottom, 1, (1 + k));
            top = r[0];
            bottom = r[1];
        }
        System.out.println(top+"/"+bottom);
    }
    public static int[] coM(int t1, int b1, int t2, int b2) {
        int[] r = new int[2];
        int b = b1 * b2;
        int t = t1 * b2 - t2 * b1;
        //约分
        if (b % t == 0) {
            b = b / t;
            t = t / t;
        } else {
            for (int i = 2; i < t; i++) {
                if (t % i == 0 && b % i == 0) {
                    b /= i;
                    t /= i;
                    i=2;
                }
            }
        }
        r[0] = t;
        r[1] = b;
        return r;

    }
}


发表于 2022-07-29 23:50:16 回复(1)
import java.util.*;

public class Main {
    
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()) {
            String str = sc.nextLine();
//        String str = "8/11";
            String[] split = str.split("/");
            int fz = Integer.valueOf(split[0]);
            String fu = split[1];
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < fz; i++) {
                sb.append(1).append("/").append(fu).append("+");
            }
            str = sb.toString();
            if (str.endsWith("+")) {
                str = str.substring(0, str.lastIndexOf("+"));
            }
            System.out.println(str);


        }


    }
}
发表于 2022-06-16 19:05:19 回复(0)