每日c/c++题 备战蓝桥杯（求解三个数的最大公约数与最小公倍数）

求解三个数的最大公约数与最小公倍数（C/C++实现）

引言

在数学计算和编程问题中，求多个数的**最大公约数（GCD）和最小公倍数（LCM）**是常见需求。本文将探讨如何高效求解三个数的GCD和LCM，并提供完整的C/C++代码实现。

基本概念

最大公约数（GCD）

两个或多个整数的最大公约数是能整除这些数的最大正整数。例如，12和18的GCD是6。

扩展到三个数：
三个数a、b、c的GCD可通过分步计算：GCD(GCD(a, b), c)。

最小公倍数（LCM）

两个或多个整数的最小公倍数是能被这些数整除的最小正整数。例如，4和6的LCM是12。

扩展到三个数：
三个数的LCM可通过分步计算：LCM(LCM(a, b), c)。

算法思路

1. GCD算法：使用欧几里得算法（辗转相除法）。

   • 计算两个数的GCD：GCD(a, b) = GCD(b, a % b)，直到余数为0。
   • 对三个数，先计算前两个数的GCD，再与第三个数求GCD。

2. LCM算法：基于公式 LCM(a, b) = |a*b| / GCD(a, b)。

   • 对三个数，先计算前两个数的LCM，再与第三个数求LCM。

代码实现（C++）

#include <iostream>
using namespace std;

// 计算两个数的最大公约数
int gcd(int x,int y)
{
    int tem = x%y;
    while(x%y)
    {
        x=y;
        y=tem;
        tem = x%y;
    }
    return y;
}

// 计算三个数的最大公约数
int gcd_three(int a, int b, int c) {
    return gcd(gcd(a, b), c);
}

// 计算两个数的最小公倍数
int lcm(int a, int b) {
    return abs(a * b) / gcd(a, b);
}

// 计算三个数的最小公倍数
int lcm_three(int a, int b, int c) {
    return lcm(lcm(a, b), c);
}

int main() {
    int a, b, c;
    cout << "请输入三个正整数：";
    cin >> a >> b >> c;
    
    cout << "最大公约数：" << gcd_three(a, b, c) << endl;
    cout << "最小公倍数：" << lcm_three(a, b, c) << endl;
    
    return 0;
}

输入输出示例

请输入三个正整数：12 18 24
最大公约数：6
最小公倍数：72

总结

• 时间复杂度：欧几里得算法的时间复杂度为 O(log(min(a, b)))，分步计算三个数的GCD/LCM仍保持高效。

• 扩展性：此方法可推广至更多数的计算（如四数、五数）。

• 注意事项：

  输入应为正整数。

  计算a*b时可能溢出，实际应用中建议使用long long类型。

  通过分治策略和数学公式的结合，我们能够简洁高效地解决多数的GCD和LCM计算问题。