概念

1.设 $a$ 和 $b$ 是两个不全为 $0$ 的整数,称 $a$ 与 $b$ 的公因子中最大的为 $a$ 与 $b$ 的最大公因子,或最大公约数,记作 $gcd(a,b)$。
2.设 $a$ 和 $b$ 是两个非零整数,称 $a$ 与 $b$ 的最小的正公倍数为 $a$ 与 $b$ 的最小公倍数,记作 $lcm(a,b)$。

性质

(1) 若 $a|m,b|m$,则 $lcm(a,b)|m$。
(2) 若 $d|a,d|b$,则 $d|gcd(a,b)$。
(3) $lcm(a,b)=\frac{ab}{gcd(a,b)}$。
(4) 设 $m,a,b$ 是正整数,则 $lcm(ma,mb)=m\times lcm(a,b)$。
(5) 若 $m$ 是非零整数 $a_1,a_2,\cdots,a_n$ 的公倍数,则 $lcm(a_1,a_2,\cdots,a_n)|m$。

我们可以使用欧几里得算法计算 $gcd(a,b)$,然后将其带入 $lcm(a,b)=\frac{ab}{gcd(a,b)}$ 即可求得 $lcm(a,b)$。

代码

最大公约数函数定义

1
2
3
4
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}

计算 $a$ 和 $b$ 的最大公约数及最小公倍数

1
2
int Gcd = gcd(a, b); // 最大公约数
int Lcm = a / Gcd * b; // 最小公倍数,先除再乘防止溢出