GCD（最大公约数）的性质
-
唯一性：对于任意两个非零整数
a和b，它们的最大公约数是唯一的。 -
非负性：GCD 总是非负的，即
gcd(a, b) ≥ 0。 -
交换性：
gcd(a, b) = gcd(b, a)。 -
结合性：
gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)。 -
分配性：
gcd(ka, kb) = k * gcd(a, b)，其中k是正整数。 -
整除性：
gcd(a, b)是a和b的公约数中最大的一个，即gcd(a, b)可以整除a和b。 -
与0的关系：如果
a是非零整数，则gcd(a, 0) = a。 -
与负数的关系：
gcd(a, b) = gcd(|a|, |b|)，即GCD不依赖于输入的符号。 -
与素数的关系：如果
p是素数，且p整除ab，则p整除a或p整除b。
LCM（最小公倍数）的性质
-
唯一性：对于任意两个非零整数
a和b，它们的最小公倍数是唯一的。 -
非负性：LCM 总是非负的，即
lcm(a, b) ≥ 0。 -
交换性：
lcm(a, b) = lcm(b, a)。 -
结合性：
lcm(a, lcm(b, c)) = lcm(lcm(a, b), c)。 -
分配性：
lcm(ka, kb) = k * lcm(a, b)，其中k是正整数。 -
整除性：
lcm(a, b)是a和b的公倍数中最小的一个，即a和b都可以整除lcm(a, b)。 -
与0的关系：如果
a是非零整数，则lcm(a, 0) = 0。 -
与负数的关系：
lcm(a, b) = lcm(|a|, |b|)，即LCM不依赖于输入的符号。 -
与GCD的关系：
gcd(a, b) * lcm(a, b) = |a * b|。
计算两个数的GCD,即最大公约数，可以使用欧几里得算法，这是一种非常高效的方法。欧几里得算法的基本思想是：
如果 a 能被 b 整除，那么 b 就是 a 和 b 的最大公约数。
否则，a 和 b 的最大公约数等于 b 和 a % b 的最大公约数。
#include <stdio.h>
// 计算两个数的GCD
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a, b;
printf("请输入两个正整数: ");
scanf("%d %d", &a, &b);
int result = gcd(a, b);
printf("GCD(%d, %d) = %d\n", a, b, result);
return 0;
}计算两个数的LCM，即最大公倍数，可以使用以下公式：
#include <stdio.h>
// 计算两个数的GCD
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 计算两个数的LCM
int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
int main() {
int a, b;
printf("请输入两个正整数: ");
scanf("%d %d", &a, &b);
int result = lcm(a, b);
printf("LCM(%d, %d) = %d\n", a, b, result);
return 0;
}*在c++中，我们也可以直接调用库函数，在调用库函数前，需要引用头文件#incluude<algorithm>
#include<algorithm>
int res = _gcd(a,b);#include<algorithm>
int res = a * b / _gcd(a,b);