最大公约数(GCD)与最小公倍数(LCM)——找到数字的共同“因数” - CSP-J

最大公约数和最小公倍数——用C++找出数字的共同“因数”

同学们，你有没有遇到过这样的问题：妈妈有两根绳子，一根长24厘米，一根长36厘米，她想把两根绳子都剪成一样长的短绳，而且每段尽可能长，不剩零头。每段最长能剪多长？这个“最长”就是最大公约数（也叫最大公因数）。反过来，如果她想用这两种绳子拼成同样长的长绳，拼出来的绳子要刚好是整数段，而且尽可能短，这个最短长度就是最小公倍数。

这两个概念不仅在生活中有用，在数学里也非常重要，比如分数化简、解应用题，甚至在C++竞赛中也经常用到。我们这就来彻底搞懂它们，并学会用C++程序一键计算。

一、什么是最大公约数（GCD）？

定义：两个整数能同时整除的最大正整数。
例如：24和36，能同时整除24和36的数有1、2、3、4、6、12，其中最大的是12，所以12就是它们的最大公约数，写作 gcd(24,36)=12。

生活例子：

你有12块巧克力，你有朋友有18块巧克力，你们想平均分给几个小朋友，每个小朋友分到的巧克力数量相同，而且不拆开整块。最多可以分给几个小朋友？答案是 gcd(12,18)=6，每个小朋友得到2块和3块。
学校合唱队男生24人，女生36人，要分成人数相等的队伍（每队男女生人数相同），最多能分几队？也是12队，每队2男3女。

C++中的辗转相除法（欧几里得算法）
这是求最大公约数最经典的方法：

用较大的数除以较小的数，得到余数。
把除数变成新的被除数，余数变成新的除数。
重复直到余数为0，此时的除数就是最大公约数。

例如求 gcd(24,36)：

36 ÷ 24 = 1 余 12
24 ÷ 12 = 2 余 0 → 除数12就是答案。

来看代码：

#include <iostream>
using namespace std;

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b != 0) {           // 当除数不为0时继续
        int temp = a % b;      // temp 存余数
        a = b;                 // 原来的除数变成新的被除数
        b = temp;              // 余数变成新的除数
    }
    return a;                  // 最后被除数就是最大公约数
}

注意：如果a或b是负数，这个算法也能工作，但通常我们只讨论正整数。可以在函数开始加上 a = abs(a); b = abs(b); 来取绝对值。

二、什么是最小公倍数（LCM）？

定义：两个整数能同时整除它们的最小正整数。
例如：4和6，能同时被4和6整除的数有12、24、36……其中最小的是12，所以12就是最小公倍数，写作 lcm(4,6)=12。

生活例子：

小明每4天去一次图书馆，小红每6天去一次，他们某天在图书馆相遇，下一次相遇至少多少天后？答案是 lcm(4,6)=12天。
你想用两种贴纸装饰班级墙报：一种长24厘米，一种长36厘米，把它们首尾相连拼成一样长的装饰条，最短需要多长？答案是 lcm(24,36)=72厘米。

公式巧算：
两个数的最小公倍数 = 两数乘积 ÷ 它们的最大公约数。
即：lcm(a,b) = a * b / gcd(a,b)

但注意：a * b 可能会很大，导致整数溢出（比如a=1000000, b=1000000时乘积会超出int范围）。所以正确写法是先除后乘：
lcm(a,b) = a / gcd(a,b) * b
这样先做除法，结果一定是个整数，再乘b就安全多了。

// 最小公倍数，先除后乘防止溢出
int lcm(int a, int b) {
    return a / gcd(a, b) * b;   // 先除以最大公约数，再乘另一个数
}

三、新手容易犯的错误

忘记处理零：如果a或b为0，gcd会怎样？按照数学定义，gcd(0, n)=n。但代码中如果b=0，while循环直接跳过，返回a，刚好就是n。但如果a=0且b!=0，循环第一次 temp = 0 % b = 0，然后a=0,b=0，最终返回0。实际上gcd(0,n)=n，所以最好在函数开头判断：if (a == 0) return b; if (b == 0) return a;
LCM溢出：直接用 a * b / gcd(a,b)，如果a和b都接近int最大值，乘积会溢出变成负数。一定要先除后乘。
循环条件写错：新手可能写成 while (b > 0)，但C++中非0即为真，写成 while (b) 也行，但 while (b != 0) 更清晰。注意不能用 while (a % b != 0)，因为循环体里a和b会变化。
负数处理：如果用户输入了负数，gcd会返回负数？比如gcd(-24,36) = ? 标准库函数通常返回正数，但我们的代码会输出-12。可以在函数开始取绝对值。

四、完整示例代码（带详细注释）

下面是一个完整的C++程序，包括输入、计算和输出。注意每一行变量定义都加了中文注释。

#include <iostream>
#include <cmath>      // 为了使用abs()取绝对值
using namespace std;

// 函数1：辗转相除法求最大公约数
int gcd(int a, int b) {
    a = abs(a);          // 取绝对值，保证结果为正
    b = abs(b);
    // 处理0的情况：0和任何数的gcd是另一个数
    if (a == 0) return b;
    if (b == 0) return a;
    
    while (b != 0) {               // 当除数不为0时循环
        int remainder = a % b;     // remainder 保存余数
        a = b;                     // 原来的除数变成新被除数
        b = remainder;             // 余数变成新除数
    }
    return a;                      // 循环结束，a就是最大公约数
}

// 函数2：利用公式求最小公倍数（先除后乘防溢出）
int lcm(int a, int b) {
    a = abs(a);
    b = abs(b);
    if (a == 0 || b == 0) return 0; // 0没有倍数，特殊处理
    return a / gcd(a, b) * b;       // 先除后乘
}

int main() {
    int x, y;                        // 定义两个整数x和y
    cout << "请输入两个整数（用空格隔开）: ";
    cin >> x >> y;

    int g = gcd(x, y);               // 计算最大公约数
    int l = lcm(x, y);               // 计算最小公倍数

    cout << "最大公约数 (GCD): " << g << endl;
    cout << "最小公倍数 (LCM): " << l << endl;

    return 0;
}

运行示例：
输入：24 36
输出：

最大公约数 (GCD): 12
最小公倍数 (LCM): 72

输入：0 15
输出：

最大公约数 (GCD): 15
最小公倍数 (LCM): 0

五、延伸学习——更多求GCD的方法

除了辗转相除法，还有更相减损术（中国古代《九章算术》中的方法）：

用大数减小数，然后差和较小数继续相减，直到两数相等。
例如：gcd(24,36)：36-24=12 → 24-12=12 → 12=12 → 答案为12。
但减法次数多，效率低，所以转辗相除法（取模）更常用。

另外，C++标准库 <algorithm> 里有一个 __gcd 函数（注意是双下划线，非标准），在竞赛中可以直接使用：

#include <algorithm>
int g = __gcd(24, 36);

不过为了更好的可移植性，自己写函数更稳妥。

六、相关知识点

质因数分解：最大公约数和最小公倍数也可以通过对每个数分解质因数来求，例如24=2³×3，36=2²×3²，取公共指数小的得gcd=2²×3=12，取指数大的得lcm=2³×3²=72。
分数化简：用gcd给分子分母同时除以最大公约数，得到最简分数。
扩展欧几里得算法：不仅能求gcd，还能求出一组整数解，用于解不定方程（比如密码学中的RSA算法）。
多个数的gcd/lcm：可以两两递归计算，例如 gcd(a,b,c) = gcd(gcd(a,b), c)。

希望这些内容能帮你牢牢掌握最大公约数和最小公倍数，下次遇到切绳子、拼积木的问题，就能用程序轻松解决啦！