蓝桥杯历届试题-核桃的数量 （C语言代码）

解题思路:
    求a1,a2,...,an的最小公倍数，可以求a1,a2的最小公倍数b1，再求b1,a3的最小公倍数b2，...，直到求出b(n-2),an的最小公倍数b(n-1)，则b(n-1)是a1,a2,...,an的最小公倍数

    这个算法不是自己想出来的，在 https://www.zhihu.com/question/40317094 有一个回答点明了这个思路

    不过应该有更优算法我还没有掌握


注意事项:





参考代码:

/*
 * 1446.c
 *
 *  Created on: 2018年2月27日
 *      Author: susu
 */

#include<stdio.h>
#include<math.h>


// 最大公约数 Greatest Common Divisor(GCD)
int FindGCD(int a, int b) {
    int r, tmp;
    if(b > a) {
        tmp = a;
        a = b;
        b = tmp;
    }
    r = a % b;
    while(r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

// 最小公倍数 Least Common Multiple(LCM)
int FindLCM(int a, int b ) {
    int r;
    r = a * b / FindGCD(a, b);
    return r;
}

int main() {
    int a1, a2, a3;
    scanf("%d%d%d", &a1, &a2, &a3);
    int b1 = FindLCM(a1, a2);
    int b2 = FindLCM(b1, a3);

    printf("%d\n", b2);

    return 0;
}