最大公约数（GCD）
是指能够同时整除两个或多个整数的最大正整数。
给定两个整数 aa 和 bb（不同时为0），它们的最大公约数 gcd(a,b)gcd(a,b) 是满足以下条件的最大正整数 dd：
dd 能整除 aa（即 amod d=0amodd=0）。
dd 能整除 bb（即 bmod d=0bmodd=0）。
对于任何其他满足前两个条件的 d′d′，有 d′≤dd′≤d。
1. 辗转相除法（欧几里得算法）
原理：gcd(a, b) = gcd(b, a % b)，直到余数为0时，除数即为GCD。
特点：高效，时间复杂度为O(log(min(a, b)))。
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
循环条件：
while (b != 0)
持续计算直到余数
b为0，此时a即为GCD。保存
b的值：int temp = b
临时存储
b，因为下一步b会被更新为余数。计算余数：
b = a % b
用
a除以b，将余数赋给b。更新
a：a = temp
将原来的
b（保存在temp中）赋给a，继续下一轮计算。返回结果：
return a
当
b=0时，a就是最大公约数。
2. 更相减损术（中国古法）
原理：gcd(a, b) = gcd(a-b, b)（a > b），直到两数相等。
特点：避免取模运算，但效率较低（最坏O(max(a, b))）。
int gcd(int a, int b) {
while (a != b) {
if (a > b) a -= b;
else b -= a;
}
return a;
}
循环条件：
while (a != b)
持续相减直到两数相等。
减法操作：
if (a > b) a -= b：若a大，则a = a - b。
else b -= a：否则b = b - a。返回结果：
return a
当
a == b时，该值即为GCD。注意事项
效率问题：若两数相差极大（如
gcd(1, 100000)），需循环多次，效率低于辗转相除法。
3. 递归实现（辗转相除法简化版）
代码简洁，但需注意栈溢出风险。
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
三元运算符：
b == 0 ? a : gcd(b, a % b)
终止条件：若
b=0，返回a。递归调用：否则计算
gcd(b, a % b)。递归过程：
每次递归将问题规模缩小，直到
b=0。
4. 二进制算法（Stein算法）
优化场景：适合大整数或硬件实现，避免乘除取模。
原理：
若a、b均为偶数：
gcd(a, b) = 2 * gcd(a/2, b/2)若a为偶数：
gcd(a, b) = gcd(a/2, b)其他情况用更相减损术。
int gcd(int a, int b) { if (a == 0) return b; if (b == 0) return a; int shift = __builtin_ctz(a | b); // 公共的2的幂次数 a >>= __builtin_ctz(a); // 移除a的2的因子 do { b >>= __builtin_ctz(b); // 移除b的2的因子 if (a > b) { int t = b; b = a; a = t; } b -= a; } while (b != 0); return a << shift; }
__builtin_ctz(x)：
GCC内置函数，返回
x的二进制表示中末尾0的个数（即因子2的幂次）。步骤解析：
步骤1：移除
a和b的所有公共2的因子（shift记录总次数）。步骤2：分别移除
a和b自身的2的因子。步骤3：用更相减损术计算奇数间的GCD。
步骤4：将结果左移
shift位（恢复公共的2的因子）。优势
避免乘除和取模运算，适合硬件实现或大整数计算。
5. 扩展欧几里得算法
额外功能：求解ax + by = gcd(a, b)的整数解(x, y)。
int extended_gcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int gcd = extended_gcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return gcd;
}
递归终止条件：
b == 0时，解为x=1, y=0（因a*1 + 0*0 = a）。递归调用：计算
gcd(b, a % b)并得到x1和y1。解的组合：
x = y1
y = x1 - (a / b) * y1满足方程：
a*x + b*y = gcd(a, b)。应用场景
求解模反元素（如RSA算法中的私钥）
6.总结
数学基础
欧几里得算法依赖定理：
gcd(a, b) = gcd(b, a mod b)。更相减损术与辗转相除法的等价性。
效率对比
辗转相除法最优（尤其大数）。
更相减损术适合硬件受限环境（无取模操作）。
边界条件
处理负数：先取绝对值（如
a = abs(a)）。零值处理：
gcd(a, 0) = |a|。
实际应用
分数化简、密码学（RSA算法）、线性同余方程求解。
进阶优化
内联函数或宏定义加速小整数计算。
使用位运算替代乘除（如Stein算法）。