exgcd

Author Avatar
ZC 1月 21, 2019
  • 在其它设备中阅读本文章

转自https://www.cnblogs.com/hadilo/p/5914302.html

欧几里得

定义: $gcd(a,b)$为整数 $a$与$b$ 的最大公约数

引理:$gcd(a,b)=gcd(b,a \bmod b)$

证明:

    设$ r=a \bmod b , c=gcd(a,b) $

    则$ a=xc , b=yc $, 其中x , y互质

    $r=a \bmod b=a-pb=xc-pyc=(x-py)c​$

    而$b=yc$

    可知:$y $与 $x-py $互质

证明:

​   假设 $y$ 与$ x-py $不互质

​   设 $y=nk , x-py=mk $, 且 $k>1 $(因为互质)

​    将 y 带入可得

​   $x-pnk=mk$

​   $x=(pn+m)k$

​    则$ a=xc=(pn+m)kc , b=yc=nkc$

​   那么此时 $a$ 与$ b $的最大公约数为 $kc $不为 $k$

​   与原命题矛盾,则 $y$ 与$ x-py $互质

    因为 $y$ 与 $x-py$ 互质,所以 $r$ 与 $b$ 的最大公约数为 $c$

    即 $gcd(b,r)=c=gcd(a,b)$

    得证

  当$a \bmod b=0$时,$gcd(a,b)=b$

  这样我们可以写成递归形式

实现:

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

扩展欧几里得

引理:存在 $x , y$ 使得$gcd(a,b)=ax+by$

证明:

当 $b=0$ 时,$gcd(a,b)=a,此时 x=1 , y=0$
当 $b \neq 0$ 时,设

$ax+by=gcd(a,b)=gcd(b,a \bmod b)=b{x}’+(a \bmod b){y}’$

$\because a \bmod b = a-a/b*b$

$\therefore ax+by=b{x}’+(a-a/b*b){y}’$

$\therefore ax+by=b{x}’+a{y}’-ba/b{y}’$

$\therefore ax+by=a{y}’+b{x}’-ba/b{y}’$

$\therefore ax+by=a{y}’+b({x}’-a/b*{y}’)​$

$解得 x={y}’ , y={x}’-a/b*{y}’$

当$b=0$ 时存在 x , y 为最后一组解

实现:

递归进入下一层,当$ b=0 $时就返回$x=1,y=0$

再根据$x={y}’ , y={x}’-a/b*{y}’$得出当前所在层的解

回到第一层的时候得到答案。

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