2025/11/12

[质数分解] - [最小公倍数] - [最大公约数] 任何一个数都可以表示为质数幂的乘积

eg.

$12 = 2^2 \times 3^1$

$8 = 2^3 \times 3^0$

GCD 被转换为对幂求最小值：

$gcd(12,8) = 2^{min(2,3)} \times 3^{min(1,0)} = 2^2 \times 3^0 = 4 $

LCM 被转换为对幂求最大值：

$lcm(12,8) = 2^{max(2,3)} \times 3^{max(1,0)} = 2^3 \times 3^1 = 24 $