花式求解：三齿轮啮合(三个数求其最小公倍数)

0x00 题目描述

在齿轮箱里三个齿轮互相衔接，某瞬间两对齿相遇，问各转多少圈后，这两对齿同时重逢。

输入：
输入数据有多组，每组数据一行，每行为3个数a,b,c，分别代表三个齿轮的齿数（均为正整数）。数与数之间用空格隔开。当a，b，c中有一个为0时，输入结束。

输出：
输出每组数据中，每个齿轮所转的圈数，用空格隔开

样例：

0x01 分析

这题因为着实比较抽象，咋一眼看，不知道该做什么（至少本蒟蒻是完全没思路）。其实稍加分析，让我们求出各转多少圈重逢实际上就是让我们求它们的最小公倍数，求出最小公倍数再除以其自身齿轮数则为答案。

0x02 解法一：暴力枚举

这个思路最简单，而且在zstuOJ上并无超时、爆长度等问题，所以这个解法适用（然后大佬们就一定会嘲笑这是个水题）。我们只需要将三数排序后，三数乘积作为for循环的上边界，最小数为下边界进行暴力枚举即可。此处附上代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int a[3],b[3];
int k,s;
int main()
{
    
    while(cin>>a[0]>>a[1]>>a[2])
    {
        b[0]=a[0];b[1]=a[1];b[2]=a[2];
        if(a[0] == 0 || a[1] == 0 || a[2] == 0)
        {break;}
      sort(a,a+3);      //升序排序
      s=a[0]*a[1]*a[2];
      k=a[2];
      for(int i=k;i<s;i++)
      {
          if(i%a[0] == 0 && i%a[1] == 0 && i%a[2] == 0)    //判断为true，则i为最小公倍数
            break;
      }
      cout<<i/b[0]<<' '<<i/b[1]<<' '<<i/b[2]<<endl;
    }
    return 0;
}

0x02 解法二：短除法

显而易见，在三个数极大的情况下，用暴力枚举就是自杀，那么，我们可以通过数论的方法，用短除法对其进行优化。下面可以通过百度百科这个例子简单的看下原理

求756，4400，19845，9000的最小公倍数？因756=223337，4400=22225511，19845=3333577，9000=22233555，这里有素数2，3，5，7，11．2最高为4次方16，3最高为4次方81，5最高为3次方125，7最高为2次方49，还有素数11。得最小公倍数为16811254911=87318000

那么，我们也可以同样的引用这个思路，通过短除，不断地削低a,b,c的值，从而降低for循环的循环次数。

下面，上代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


#include<cstdio>
#include<iostream>
using namespace std;
int a,b,c,bj=1,maxNum,lcm;      //Least Common Multiple 
int d[3];
int max(int x,int y,int z);
int main(){
    while(cin>>d[0]>>d[1]>>d[2]){
        a = d[0];b = d[1];c = d[2];         //保留原数
        if(a == 0 or b == 0 or c == 0)
            break;
        maxNum = max(a,b,c);
        lcm = 1;
        for(int i=2;i<=maxNum;i++){
            bj = 1;
            while(bj){
                bj = 0;
                if(a%i == 0){
                    a = a/i;
                    bj = 1;
                }
                if(b%i == 0){
                    b = b/i;
                    bj = 1;
                }
                if(c%i == 0){
                    c = c/i;
                    bj = 1;
                }
                if(bj == 1)
                    lcm *= i;
            }
            maxNum = max(a,b,c);      //此步极其关键
        }
        cout<<lcm/d[0]<<" "<<lcm/d[1]<<" "<<lcm/d[2]<<endl;
    }
    return 0;
}

int max(int x,int y,int z){
    if(x>=y && x>=z)
        return x;
    else if(y>=x && y>=z)
        return y;
    else
        return z;
}

0x02 解法三：函数嵌套与欧几里得算法

这个方法同样也是用数论降低其循环次数，以压低耗时。

根据最小公倍数定义：(a,b最大公约数)x[a,b最小公倍数]=ab(a,b均为整数) 进行移项，可得 [a,b最小公倍数]=ab/(a,b最大公约数)，那么问题就变换成了求两两数之间的最大公约数，然后根据最小公倍数性质，可通过函数的嵌套以求出三个数之间的最小公倍数。而两数间的最大公约数可用欧几里得算法（辗转相除法）轻易求出。

欧几里得算法定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

代码非常简单，短短三十行

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include <iostream>       //欧几里得算法（辗转相除法）
#include <cmath>
using namespace std;
int a[3];
int k,s,ans;
int lcm(int x,int y);
int main()
{
    
    while(cin>>a[0]>>a[1]>>a[2])
    {
        if(a[0] == 0 or a[1] == 0 or a[2] == 0)
            break;
        
        ans = lcm(lcm(a[0],a[1]),a[2]);    //函数嵌套
        cout<<ans/a[0]<<" "<<ans/a[1]<<" "<<ans/a[2]<<endl;
    }
    return 0;
}

int lcm(int x,int y){
    int t1,t2,t3;
    t1 = x;
    t2 = y;
    t3 = t1%t2;
    while(t3 != 0){
        t1 = t2;
        t2 = t3;
        t3 = t1%t2;
    }
    return x*y/t2;
}

然后，我还看到csdn上不少大佬将gcd函数改写为递归，不过个人感觉没有太大的必要，虽然再次压了行数，但是代码的易读性被牺牲了。（或许这也是我弱的原因吧…）