最大公约数与最小公倍数

概念

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)$。

代码

最大公约数函数定义

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

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

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