求最小公倍数

2019-04-26 本文已影响0人 zju_dream

最小公倍数的求解在最大公约数的基础上进行的
最小公倍数： $a*b/d$
为什么是上方的公式，可以结合下方的图进行理解。a和b的最大公约数即集合a和集合b的交集，而最小公倍数为a和b的并集。要得到并集，由于ab会使共因子部分多计算一次，因此需要除掉一次共因子，于是得到了上式。（由于ab在实际计算时可能溢出，因此更恰当的写法为 $a/d * b$ ）
image.png