GCD与LCM及其部分性质

GCD

GCD,即最大公约数,指两个或多个整数共有约数中最大的一个。

求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。

在一般竞赛中,求GCD一般使用辗转相除法。其复杂度约为O(log(max(n,m))),是一种很高效的算法。而且其代码量也非常少

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

拓展性质

如果GCD( n , a ) = 1 , n>a 则GCD( n , n - a ) = 1。

可以用反证法证明

假设GCD( n , n - a ) = i ( i > 1 ),设 n = k1 * i,n - a = k2 * i( k1 > k2 > 0 ),

则 n -( n -a ) = a = (k1-k2) * i,与GCD( n , a ) = 1 矛盾,所以上述性质成立。

扩展欧几里得算法

设a , b为常数,对于一个表达式 a * x + b * y =GCD( a , b ) ,一定存在解( x , y)使之成立。

我们就可以通过扩展原来的辗转相除法来求解。

求解的过程如下(最好自己手推一下):

初始表达式
$$
a * x + b * y =GCD( a , b )
$$
由之前的知识可得
$$
GCD( a , b ) =GCD( b , a \% b )
$$
因此
$$
a*x_1+b*y_1=GCD( a , b ) =GCD( b , a\%b ) =b*x_2+(a\%b)*y_2
$$

$$
a\%b=a-[a/b]*b
$$

其中[a/b]表示整除。带入化简可得:
$$
a*x_1+b*y_1=a*y_2+b*(x_2-[a/b]*y_2)
$$
由恒等关系可得
$$
x_1=y_2
$$

$$
y_1=x_2-[a/b]*y_2
$$

因此我们只要求出 x2 和 y2 的值就可以求解 x1 和 y1。而 x2 , y2 可通过同种方法求解。

特别的,当 b=0时,表达式为 a * x + b * y = GCD( a , b ) =GCD( a , 0 ) = 0

此时,可求得 x = 1 。y 的值对表达式的值没有影响。

上面就是求解初始表达式的方法。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
int extGcd(int a,int b,int &x,int &y)//这里取 x , y的地址 
{
if(b==0)
{
x=1;y=0;
return a;//函数的返回值一直是 gcd(a,b)
}
int r=exGcd(b,a%b,x,y);
int t=x;
x=y; //x1=y2
y=t-a/b*y; //y1=x2-[a/b]*y2
return r;
}

LCM

LCM,即最小公倍数,指两个或多个整数共有倍数中最小的一个。

LCM的求法可以基于GCD的基础上:
$$
LCM(a,b)=a*b/GCD(a,b)
$$
证明略。

一般题目求解时使用GCD更多一些,所以LCM相关知识就不多写了。(我也没找到太多关于LCM的相关文献)

感谢您的支持
-------------本文结束感谢您的阅读-------------