题目描述 Description

　　任何一个[0,1]中的有理数p/q(p、q均为自然数)一定可以分解成1/r1+1/r2+1/r3+…+1/rk，且r1<r2<r3<…<rk。当然这样的分解不是唯一的，如5/6=1/2+1/3=1/2+1/5+1/8+1/120，第一个分解式中的第二项比第二个分解式中的第二项大，因此我们可以定义第一个分解式比第二个分解式大。

　　程序要求找出p/q的最大分解式。

 输入输出格式 Input/output

输入格式：

键盘输入p、q，1≤p≤q≤50

输出格式：

从小到大依次输出分解式中的每个分母，一行输出一个数

 输入输出样例 Sample input/output

样例测试点#1

输入样例：

5 6

输出样例：

2 3

思路：

假设1/r是能从p/q中分解出来的最大分子为1的真分数，则1/r≤p/q＜1/(r-1)①

又因为p/q-1/r=(p×r-q)/(q×r)②

根据①可知，p×(r-1)<q，所以p×r-p＜q，代入②中可看出，每次待分解的分数的分子一定单调下降，所以就可以用单精度除法(高精度除以普通整数)解决本题。

注意：在输入p、q后要对分数进行化简。

 

代码如下：

1 #include 
     
       2 int gcd(int a,int b)//求最大公约数 3 { 4     int r=a%b; 5     while(r>0) 6     { 7         a=b; 8         b=r; 9         r=a%b;10     }11     return b;12 }13 int main()14 {15     int p,q;16     int cm;//当前最大公约数 17     int r;18     scanf("%d%d",&p,&q);19     while(p>0)20     {21         cm=gcd(p,q);22         if(cm>0)23         {24             /*===========*///化简分数 25             p=p/cm;26             q=q/cm;27             /*===========*/28         }29         if((q%p)>0)//如果不能分解为最终的1/rk 30         {31             r=q/p+1;32         }33         else34         {35             r=q/p;36         }37         printf("%d\n",r);38         p=p*r-q;//减掉 39         q=q*r;40     }41     return 0;42 }