锦溪网站建设/html网页设计模板
求最大公约数（GCD）与最小公倍数（LCM）
1. 基本概念
- GCD（最大公约数）：两个整数的最大公共因数
- LCM（最小公倍数）：两个整数的最小公共倍数
- 数学关系：
LCM(a,b) = (a × b) / GCD(a,b)
2. C++实现方法
方法一：使用STL的gcd函数（C++17起）
#include <iostream>
#include <numeric> // 包含gcd和lcm函数int main() {int a = 56, b = 98;// C++17标准库函数int gcd_result = std::gcd(a, b);int lcm_result = std::lcm(a, b);std::cout << "数字: " << a << " 和 " << b << "\n";std::cout << "GCD: " << gcd_result << "\n";std::cout << "LCM: " << lcm_result << "\n";return 0;
}
方法二：自定义实现（欧几里得算法 / 辗转相除法）
欧几里得算法基于以下核心原理：
两个整数的最大公约数（GCD）等于其中较小数与两数相除余数的最大公约数
数学表达式：
gcd(a, b) = gcd(b, a mod b)
持续递归/迭代，直到余数为0时，此时的除数即为最大公约数
关键引理
若 a = b*q + r（其中 q 是商，r 是余数），则：
gcd(a, b) = gcd(b, r)
证明过程
- 设
d = gcd(a, b)，则d|a且d|b（d能整除a和b） - 因为
r = a - b*q，所以d|r（d也能整除余数） - 因此d是
b和r的公约数 - 反过来证明
gcd(b,r)也是a和b的公约数 - 故两者相等
#include <iostream>
#include <cstdlib> // 用于abs函数
using namespace std;// 递归实现GCD
int gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b); //被除数b如果等于0那么就返回a，不等于0就返回b除a%b
}// 迭代实现GCD
int gcd_iterative(int a, int b)
{while (b) {a %= b;swap(a, b);}return a;
}// 计算LCM
int lcm(int a, int b)
{return abs(a * b) / gcd(a, b);
}int main() {int x = 56, y = 98;cout << "自定义实现:\n";cout << "GCD(" << x << ", " << y << ") = " << gcd(x, y) << "\n";cout << "LCM(" << x << ", " << y << ") = " << lcm(x, y) << "\n";return 0;
}
注意事项
处理负数：建议先取绝对值
处理零值：gcd(a,0) = |a|，lcm(a,0) = 0
溢出问题：大数计算时考虑使用long long
补充：二进制GCD算法（Stein算法）
迭代版
int binary_gcd(int a, int b) {if (a == 0) return b;if (b == 0) return a;// 移除公共的2因子int shift = __builtin_ctz(a | b);a >>= __builtin_ctz(a);do {b >>= __builtin_ctz(b);if (a > b) swap(a, b);b -= a;} while (b != 0);return a << shift;
}
递归版
int binary_gcd(int a, int b) {if (a == b) return a;if (a == 0) return b;if (b == 0) return a;if (~a & 1) { // a是偶数if (b & 1) // b是奇数return binary_gcd(a >> 1, b);else // 都是偶数return binary_gcd(a >> 1, b >> 1) << 1;}if (~b & 1) // a奇b偶return binary_gcd(a, b >> 1);// 都是奇数return (a > b) ? binary_gcd((a-b)>>1, b) : binary_gcd((b-a)>>1, a);
}