GCD

Author Avatar
洛水·锦依卫 1月 25, 2019

GCD

GCD-欧几里得定理(辗转相除)

原理

$GCD(a,b)=GCD(b,a\%b)$

证明

设$a=bk+c$,显然有$c=a\%b$。设$d|a\ \ \ d|b$,则

由右边的式子可知$\frac{c}{d}$为整数,即$d|c$所以对于$a,b$的公约数,它也会是$a\%b$的公约数。

反过来也需要证明

设$d|b\ \ \ d|(a\%b)$,我们还是可以像之前一样得到以下式子

因为左边式子显然为整数,所以$\frac{a}{d}$也为整数,即$d|a$,所以$b,a\%b$的公约数也是$a,b$的公约数。

既然两式公约数都是相同的,那么最大公约数也会相同

所以得到式子

使用

所以我们可以写出一个递归式,层层深入,直到 $b%(a%b)==0$,即正好为倍数整除时,递归回去就行了

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

最后的返回值自然为$a,b$的最大公因数

EXGCD-扩展欧几里得定理

目的:求$ax+by=gcd(a,b)$的一组可行解

证明

由欧几里得定理可知:

所以

又因为

所以

因为$a=a,b=b$,所以

将$x_2,y_2$不断代入递归求解直至$GCD$为0递归$x=1,y=0$回去求解,就像$GCD$一样的方法

int Exgcd(int a,int b,int &x,int &y)
{
    if (!b) 
    {
        x=1;y=0;
        return a;
    }
    int d=Exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}

返回的值为$GCD$,在这个过程中计算$x,y$即可