数论---lcm和gcd

cd即最大公约数，lcm即最小公倍数。

首先给出a×b=gcd×lcm

证明：令gcd(a,b)=k,a=xk,b=yk,则a×b=xykk，而lcm=xyk，所以ab=gcd*lcm。

所以求lcm可以先求gcd，而求gcd的方法就是辗转相除法，也叫做欧几里德算法，核心为gcd(m,n)=gcd(n,m%n)
递归实现：
‘‘‘
LL gcd(LL a, LL b){
return b ? gcd(b, a%b) : a;
}
‘‘‘
while循环:
‘‘‘
LL gcd(LL a, LL b){
LL t;
while(b){
t = b;
b = a % b;
a = t;
}
return a;
}
‘‘‘

数论---lcm和gcd

原文：https://www.cnblogs.com/ACMerLwy/p/11647373.html