以
的格式输入一个分数
,其中
。不保证分数为最简分数。
以
的格式输出结果,其中,
表示每一个埃及分数的分母。
如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
2/4
1/2
在这个样例中,输出
也是正确的。
8/11
1/2+1/5+1/55+1/110
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); } } }
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); } } }
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)); } } }
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; } }
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(); } }
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); } } }
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); } } }
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()); } } }
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); } } }
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; } }
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()); } } }
//这都行 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); } }
//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; } }