GCD LCM

本文主要是介绍GCD LCM，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

GCD(最大公约数)

欧几里得算法(辗转相除法)

原理

if(a%b==0) GCD=b 
else GCD=b%(a%b)

设$a\ge b$：
若$a\mathrm{mod}b==0$，则$gcd(a,b)==b$(整除性质)；
若$a\mathrm{mod}b!=0$，则$gcd(a,b)==gcd(b,a\mathrm{mod}b)$(辗转相除)。

实现

extern int m,n;//已在其他位置定义m:被除数 n:除数

非递归算法

int gcd(int m,int n){int r;//暂存余数do{r=m%n;if(r!=0){m=n,n=r;}}while(r!=0);return n;
}

递归算法

int gcd(int m,int n){if(n==0) return m;else return gcd(n,m%n);
}

对于C++17，可以使用内置函数__gcd

lcm(最小公倍数)

$a\ast b==gcd(a,b)\ast lcm(a,b)$

$\Rightarrow$ $lcm(a,b)==\frac{a\ast b}{gcd(a,b)}$

int lcm(int a,int b){return a/gcd(a,b)*b;
}

这篇关于GCD LCM的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---