C++最大公约数（GCD）
困难29最大公约数：原来数学可以这么简单！
什么是最大公约数？
假如你和同桌一起买零食，你有 12 块巧克力，同桌有 18 块饼干。你们想把它们平均分成几袋，每袋里巧克力和饼干的数量相同，而且每袋里的总数要尽可能多。那么每袋最多能装多少块零食？答案是 6 块（3 块巧克力+3 块饼干），因为 12 和 18 的最大公约数就是 6。
最大公约数（Greatest Common Divisor，简称 GCD）就是指几个数共有的因数中最大的那个。它就像“最大公共因子”，能帮我们解决分组、通分、化简分数等很多问题。比如分数 4/6 和 8/12，分子分母的公共因数分别是 2 和 4，最大的是 4，所以化简后都是 1/3？等等，4/6 分子分母同除以 2 得 2/3，8/12 同除以 4 得 2/3，它们相等！最大公约数在这里就是化简时“一次性除到底”的关键。
怎么用数学方法求出最大公约数？
方法一：列举公因数（适合小数字）
要找到 12 和 18 的最大公约数，可以先列出每个数的所有因数：
- 12 的因数：1, 2, 3, 4, 6, 12
- 18 的因数：1, 2, 3, 6, 9, 18
相同的因数有：1, 2, 3, 6。最大的那个是 6，所以 GCD(12,18)=6。
不过数字大了这样列举就很麻烦，比如求 252 和 180 的 GCD，总不能一个个列吧？别急，有聪明的办法。
方法二：辗转相除法（欧几里得算法）
这个方法两千多年前就被欧几里得发现了，核心思想是：
两个数的最大公约数，等于较小的数和两数相除的余数的最大公约数。
听起来有点绕，看例子就明白了：
求 GCD(18, 12)：
- 18 ÷ 12 = 1 余 6（余数 6）
- 问题变成求 GCD(12, 6)
- 12 ÷ 6 = 2 余 0（余数为 0）
- 当余数为 0 时，当前的除数（6）就是答案。
再试一个：求 GCD(252, 180)
- 252 ÷ 180 = 1 余 72
- 180 ÷ 72 = 2 余 36
- 72 ÷ 36 = 2 余 0 → 最大公约数是 36。
这个算法就像“两个数不停互相取模，直到余数为 0”，最后剩下的非零除数就是 GCD。是不是很神奇？
用 C++ 实现辗转相除法
方法一：循环实现（推荐）
循环是最好理解的写法。我们一步步来：
#include <iostream>
using namespace std;
int gcd(int a, int b) { // 返回a和b的最大公约数
while (b != 0) { // 只要b不为0就继续
int remainder = a % b; // 存下余数
a = b; // 把除数变成新的被除数
b = remainder; // 把余数变成新的除数
}
return a; // 当b为0时，a就是最大公约数
}
int main() {
int x, y; // 两个输入的数字
cout << "请输入两个正整数：";
cin >> x >> y;
cout << "最大公约数是：" << gcd(x, y) << endl;
return 0;
}
为什么不用先判断谁大谁小？
假如你输入 12 和 18，a=12, b=18，第一次循环：12 % 18 = 12（余数 12），然后 a=18, b=12——这不就自动换过来了吗？所以任何顺序都可以。
生活中的例子：你有一个 24 格的冰格和 60 块小积木，想摆成每行积木数相同且占满冰格，每行最多摆几块？求 GCD(24,60) = 12，没错。
方法二：递归实现（更简洁）
递归就是函数调用自己，写法更“数学化”：
int gcd(int a, int b) { // 返回a和b的最大公约数
if (b == 0) { // 终止条件：如果b为0，a就是结果
return a;
}
return gcd(b, a % b); // 递归：把较小的和余数继续算
}
小提示：递归虽然漂亮，但如果数字非常大（比如上百万），递归层数可能很深，有栈溢出的风险。平时用小数字没问题，但循环更稳健。
新手最容易犯的错误
错误1：忘记处理 0 的情况
如果输入 0 和 6，正确的 GCD 应该是 6（因为 0 能被任何非零数整除）。我们的循环写法能处理吗？
- 输入 a=0, b=6，第一次循环：0 % 6 = 0，a=6, b=0，循环结束，返回 a=6。正确！
- 但如果输入 a=6, b=0，循环一开始 b==0，不会执行，直接返回 a=6。也没问题。
但如果程序里用了递归，并且忘记写 if (b==0) 的终止条件，就会死循环。
错误2：输入负数导致死循环
C++ 的取模 % 对负数结果可能是负数。比如 -12 % 5 = -2，这样循环永远不会变成 0。
解决办法：先把负数转为正数：a = abs(a); b = abs(b);（别忘了 #include <cmath>）。
错误3：混淆参数顺序，导致计算错误（仅限某些不严谨的实现）
如果自己写了一个“先比较大小再交换”的版本，忘了交换就会算错。但用我们上面的循环或递归，顺序无所谓。
错误4：忘记用 long long 处理大数
两个 int 相乘可能超过 2^31-1，比如求 2000000000 和 1500000000 的 GCD，没问题，但如果是求最小公倍数（后面会讲）需要乘法，这时要用 long long。
完整示例：计算分数化简
来一个实用程序：输入一个分数（分子分母），输出化简后的分数。
#include <iostream>
#include <cmath> // 用来取绝对值
using namespace std;
int gcd(int a, int b) { // 计算a和b的最大公约数
a = abs(a); // 避免负数干扰
b = abs(b);
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
int main() {
int numerator, denominator; // 分子, 分母
cout << "请输入分子和分母（用空格隔开）：";
cin >> numerator >> denominator;
if (denominator == 0) {
cout << "分母不能为0！" << endl;
return 1;
}
int common = gcd(numerator, denominator); // 最大公约数
numerator /= common; // 分子约分
denominator /= common; // 分母约分
cout << "化简后的分数是：" << numerator << "/" << denominator << endl;
return 0;
}
运行：
请输入分子和分母（用空格隔开）：24 36
化简后的分数是：2/3
相关知识点：最小公倍数（LCM）
知道了最大公约数，最小公倍数（LCM）就很简单了：两个数的乘积除以它们的最大公约数。
LCM(a, b) = a * b / GCD(a, b)
比如 a=12, b=18，GCD=6，那么 LCM=12*18/6 = 36。为什么？因为 12=2×6，18=3×6，乘积里包含了“公共部分”6 的两倍，除掉一次 6 就得到最小公倍数。
应用场景：你和同桌分别每隔 12 天和 18 天去一次图书馆，下一次一起去是什么时候？就是最小公倍数 36 天后。
用代码实现很简单：
long long lcm(int a, int b) { // 返回最小公倍数，用long long防止溢出
return (long long)a / gcd(a, b) * b; // 先除后乘，减少溢出风险
}
你还可以用同样的辗转相除法求多个数的 GCD（两两计算），也可以用来解更复杂的数论问题，比如判断互素（GCD=1）、简化循环小数等。
继续探索：如果你对数学和编程感兴趣，可以学习“更相减损术”（中国古代算法）、“扩展欧几里得算法”（解不定方程）等，它们都是在 GCD 基础上的巧思。
现在，拿两个数字试试吧！比如算算你自己生日和同桌生日的最大公约数（开玩笑啦～），或者算算你攒的零花钱和同桌的零花钱能分成多少份相同数量的礼物！?
例题精讲
辗转相除法（欧几里得算法）是计算最大公约数的经典方法。已知两个正整数a和b（a > b），则gcd(a, b)等于以下哪一项？
若要用递归函数实现计算最大公约数，以下哪个递归终止条件是正确的？（假设a、b均为非负整数，且不同时为0）
用更相减损法计算两个数的最大公约数时，如果两个数都是偶数，可以先提取公因子2，简化计算。
以下代码使用while循环实现欧几里得算法（辗转相除法）求最大公约数，请将空白处补充完整。
int gcd(int a, int b) {
while (b != 0) {
int temp = ___;
a = b;
b = temp;
}
return a;
}以下递归函数用于计算两个非负整数a和b的最大公约数，请将空白处补充完整。
int gcd(int a, int b) {
if (b == 0) return a;
return ___;
}