最大公约数&最小公倍数

Zlc晨鑫 · 2020-10-10 10:44:58 · 个人记录

给出a和b，求a和b的最大公约数和最小公倍数。

设gcd(a, b)为a和b的最大公约数。

• 辗转相除法：gcd(a, b)=gcd(b, a \% b)直到a\%b=0，b即为答案.
• 辗转相减法：gcd(a, b)=gcd(max(a, b)-min(a, b), min(a, b))直到a=b，a或b即为答案（a=b）.

最小公倍数= a\times b \div gcd(a, b).

注：辗转相除法又称欧几里得算法。辗转相减法可用于高精度整数求最大公约数。