数学gcd全称,数学日记

本系列文章内容大多采集yjdfj著作：《算法竞赛入门到进阶》 清华大学出版社， 感谢yjdfj的支持。

最大公约数GCD和最小公倍数LCM是竞赛中常见的知识点，虽然这两个知识点很容易理解，但往往会与其他知识点结合起来出综合题就不容易。
1.最大公约数GCD

整数a和b的最大公约数记为gcd(a,b)。在编程时候有两种写法。 （1）经典的xxdxrz算法，用辗转相除法求最大公约数，模板如下： int gcd(int a,int b){return b == 0 ? a:gcd(b,a%b);}

时间复杂度差不多是O(㏒₂ⁿ)，非常快。

（2）或者直接用C++的内置函数求GCD：

std::__gcd(a,b)

2.最小公倍数LCM
整数a和b的最小公倍数记为lcm(a,b)，模板如下：

int lcm(int a, int b){return a/gcd(a,b)*b;//最小公倍数=两数之积÷两数最大公约数}