Position：

• * http://acm.swust.edu.cn/problem/0626/ *

---

• SWUST626 分数分解

  • List

  • Description

  • Input

  • Output

  • Sample Input

  • Sample Output

  • Solution

  • Code

  • 变式

    　　分子为1 的分数称为埃及分数，现输入一个真分数，请将该分数按下面的方法分解为埃及分数: 1.若真分数的分子a能整除分母b，则真分数经过化简就可以得到埃及分数; 2.若真分数的分子不能整除分母，则可以从原来的分数中分解出一个分母为b/a+1的埃及分数; 3.用这种方法将剩余部分反复分解，最后可得到结果。如：8/11=1/2 + 1/5 + 1/37 + 1/4070。

一个分数如A/B的形式

见SAMPLE OUTPUT，注意空格位置在加号前后都有

3/88

1/30 + 1/1320

数学家斐波那契提出的一种求解埃及分数的贪心算法 
设a、b为互质正整数，a < b 分数a/b 可用以下的步骤分解成若干个单位分数之和： 
步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1） 
步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r)/b(q1+1） 
步骤三：重复步骤2，直到分解完毕 
EG . 
3/7=1/3+2/21=1/3+1/11+1/231 
13/23=1/2+3/46=1/2+1/16+1/368

// <0626.cpp> - Wed Sep 28 15:00:44 2016
// This file is made by YJinpeng，created by XuYike's black technology automatically.
// Copyright (C) 2016 ChangJun High School, Inc.
// I don't know what this program is.

#include
#include
using namespace std;
int main()
{
freopen("0626.in","r",stdin);
freopen("0626.out","w",stdout);
int a,b,c;
while(~scanf("%d/%d",&a,&b)){
while(b%a){
c=b/a+1,a=a*c-b,b=b*c;//a/b-1/c=ac-b/bc
printf("1/%d + ",c);
}
printf("1/%d\n",b/a);
}
return 0;
}

这道题的变式:Codevs 1288 埃及分数