最大公因数与最小公倍数-gcd&lcm

一、一些性质

　　 \(gcd(a,b)=gcd(b,a)\)

　　 \(gcd(-a,b)=gcd(a,b)\)

　　 \(gcd(a,a)=|a|, gcd(a,0)=|a|\)

　　 \(gcd(a,1)=1\)

　　 \(gcd(a,b)=gcd(b, a mod b)\)

　　 \(gcd(a,b)=gcd(b, a-b)\)

　　 \(gcd(a,b)*lcm(a,b)=ab\)

　　 \(a|t,b|t⇒lcm(a,b)\)

　　 \(...\)

二、最大公约数-gcd

1.欧几里得辗转相除法

证明：

　　 设\(a=qb+r\)，\(d|a\)且\(d|b\),

　　 \(∵a=qb+r,\)

　　 \(∴r=a-qb,\)

　　 \(∵d|a\)且\(d|b\)

　　 \(∴d | a -qb\)

　　 \(∴d | r\)

　　 \(∴a,b\)的公因数都是\(b,r\)的公因数

　　 \(∴gcd(a,b)=gcd(b,r)\)

代码实现：

int gcd(int a, int b){
  return b == 0 ? a : gcd(b , a % b);          
}
      

2.stein_gcd算法

int stein(int a, int b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (a % 2 == 0 && b % 2 == 0) return stein(a >> 1, a >> 1) * 2;  //当两数均为偶数时将其同时除以2至至少一数为奇数为止，记录除掉的所有公因数2的乘积k
  else if (a % 2 == 0) return stein(a >> 1, b);  //因为只有一个数含有2作为因数，所以除以2后gcd(a,b)不变
  else if (b % 2 == 0) return stein(a, b >> 1);  //同上
  else return stein(abs(a - b), min(a, b));   //详情请查看'更相减损数'                              
}
      

三、最小公倍数-lcm

基于gcd(a,b)*lcm(a,b)=ab这条性质则可求出最小公倍数
      

好像stein算法不是很常用，但的确弥补了欧几里得算法的一些缺点