GCD-LCM

GCD-最大公约数

辗转相除法：两个数的最大公约数等于其中较小的数字和二者之间余数的最大公约数

假设有两个数字[12921，4234]。 将两数中较大的那一个看作是被除数A，将较小的那一个看作是除数B 二者相除的商记作C，余数记作D。这样我们就可以得到一个等式：

​ A = B×C + D

而辗转相除法的所要用到的原理则是：(A , B) = (B , D)

(12921,4234) -> (4234,219) -> (219,73) -> (73,0)

当较小的那个数为0时，较大的那个数就是最大公约数

c++函数如下：

int gcd(int x,int y){ //适当的时候，int换成ll
	if (x < y)
		swap(x,y); //确保x大于y
	if (y == 0)
		return x; //y == 0时，返回x
	else
		return gcd(y,x%y); //y ！= 0，继续运算
}

简写：

int gcd(int x, int y){
	return y == 0 ? x : gcd(y, x%y);
}

库函数

#include <algorithm>
inline int gcd(int a,int b) {
	return __gcd(a,b);
}

LCM-最小公倍数

若要求最小公倍数，只需要将两数的乘积除以最大公约数就可以。

int lcm(int x,int y){  //两个数的最小公倍数等于乘积/最大公约数
	return (x*y)/gcd(x,y); 
}