两个分数的最小公倍数

Tips: 本文中所求的最小公倍数的对象都是正数！

在求两个分数的最小公倍数之前，我们可以先来回顾一下如何求两个自然数的最小公倍数：

1. 两个自然数的最小公倍数

假设已知两个自然数a和b,求两者的最小公倍数 f(a,b):

（1）如果两个数互质，那么易知最小公倍数为

f(a,b) = a*b;

（2）如果两个数有公约数，不妨设一共有N个公约数，每个公约数为gi(a,b) (i=1~N)，那么可知两者的乘积 a*b，必定包含gi(a,b)，

那么最小公倍数必定为

f(a,b)= min a*b/gi(a,b); // i=1~N

设gcd(a,b) 为a和b的最大公约数，则有

f(a,b) = a*b/gcd(a,b);

又有，如果a和b互质，那么必有gcd(a,b)=1

所以，任意两个整数a和b的最小公倍数求解公式为

f(a,b) = a*b/gcd(a,b);   // a,b为任意自然数

2. 两个分数的最小公倍数

2.1 易知任意自然数都能表示成分数形式，例如自然数a，可以表示成

a = a*N/N;  // N为任意非零整数

那么求任意两个整数a和b的最小公倍数，可以转换成：

a = a*N1/N1;   // N1为任意正整数
b = b*N2/N2;   // N2为任意正整数

// 通分
a = a*N1*N2/ N1*N2;
b = b*N2*N1/ N2*N1;

//分别对分子和分母求最小公倍数

f1(a,b) = (a*N1*N2) * (b*N2*N1) / gcd(a*N1*N2, b*N1*N2); //分子最小公倍数

f2(a,b) = (N1*N2)*(N1*N2)/ gcd(N1*N2, N1*N2); // 分母最小公倍数

// 化简得
f1(a,b) = a*b*N1*N2/gcd(a,b);
f2(a,b) = N1*N2;

// 结果
f(a,b)  =  a*b / gcd(a,b);

2.2 若a和b为两个真分数，那么怎么求两者的最小公倍数方法可以参考2.1中的方法：

（1）分别对a和b进行通分

（2）对通分后的a和b的分子和分母分别求最小公倍数f1,f2

（3） f= f1/f2 对结果进行约分，即可得到最终结果

例如：

已知 a = 9/4  b= 4/3 ,求两者的最小公倍数

(1) 通分  a = 27/12  b = 16/12
(2) 分别求分子和分母的最小公倍数

     f1 = 27*16/gcd(27,16) = 432
     f2 = 12

(3)  f = f1/f2= 432/12 = 36

3. 优化方法：

从上面可以看到通分这个步骤需要多次进行乘法操作，如果数字过大，则可能出现超过数据范围，能否简化，减少乘法的次数呢？

如果不通分，该怎么做呢？

(1) 对a和b的分子进行最小公倍数 f1

(2) 求a和b的分母的最小公约数g1

(3) f = f1/g1 化简之

例如：

已知 a = 9/4  b= 4/3 ,求两者的最小公倍数

// 通分法
(1) 通分  a = 27/12  b = 16/12
(2) 分别求分子和分母的最小公倍数
     f1 = 27*16/gcd(27,16) = 432
     f2 = 12
(3)  f = f1/f2= 432/12 = 36

// 优化法

(1) f1 = 9*4/gcd(9,4) =36;
(2) g1 = gcd(4,3) =1;
(3) f = f1/g1 = 36

具体的理论证明略。

练习题：http://acm.hdu.edu.cn/showproblem.php?pid=1713

code如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 int la,ra,lb,rb,num,temp1,temp2,res;
 6 
 7 int gcd(int a,int b)
 8 {
 9      if(a*b==0) return 0;
10      if(a%b==0) return b;
11      return gcd(b,a%b);
12 }
13 
14 int main()
15 {
16     int T,i,lsa,lsb;
17     char c1,c2;
18     scanf("%d",&T);
19     while(T--)
20     {
21        scanf("%d/%d %d/%d",&la,&ra,&lb,&rb);
22        
23        // 化简表达式A 
24        temp1= gcd(la,ra);
25        la/=temp1;
26        ra/=temp1;
27        
28        // 化简表达式B 
29        temp2 = gcd(lb,rb);
30        lb/=temp2;
31        rb/=temp2;
32        
33        // 求分子的最小公倍数 
34        temp1 = gcd(la,lb);
35        res= la/temp1*lb;
36        
37        // 求分母的最大公约数 
38        temp2 = gcd(ra,rb);
39        
40        // 对结果约分 
41        temp1 = gcd(res,temp2);
42        res /=temp1;
43        temp2/=temp1;
44        
45        if(temp2==1) printf("%d
",res);
46        else
47            printf("%d/%d
",res,temp2);
48     }
49     return 0;
50 }

1713

转载请注明出处：http://www.cnblogs.com/double-win/ 谢谢！