扩展欧几里得定理 —— ylxmf2005的OI教程

裴蜀定理

定义

什么是裴蜀定理?

裴蜀定理,又称贝祖定理(Bézout’s lemma)。是代数几何中一个定理。

其内容是:

设 $a,b$ 是不全为零的整数,则存在整数 $x,y$ , 使得 $ax+by=\gcd(a,b)$ .

证明

  1. 若任何一个等于 $0$ , 则 $\gcd(a,b)=a$ . 这时定理显然成立。

  2. 若 $a,b$ 不等于 $0$ .

    由于 $\gcd(a,b)=\gcd(a,-b)$ ,

    不妨设 $a,b$ 都大于 $0$ , $a\geq b,\gcd(a,b)=d$ .

    对 $ax+by=d$ , 两边同时除以 $d$ , 可得 $a_1x+b_1y=1$ , 其中 $(a_1,b_1)=1$ .

    转证 $a_1x+b_1y=1$ . 由带余除法:

    $\begin{aligned}a_1 &= q_1b+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned}$

    于是,有

    $\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1$


    $r_{n-2}=x_nr_{n-1}+1$


    $1=r_{n-2}-x_nr_{n-1}$

    由倒数第三个式子 $r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}$ 代入上式,得$1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}$

    然后用同样的办法用它上面的等式逐个地消去 $r_{n-2},\cdots,r_1$ ,

    可证得 $1=a_1x+b_1y$ .

例题

[HAOI2011]向量

P1072 Hankson 的趣味题

CF510D Fox And Jumping

扩展欧几里得定理

定义

用于

  • 求$ax+by=c$的一组解或最小的解?

  • 求解同余方程的一组解或最小的解?

实现

引理

辗转相除法 $gcd(a,b)=gcd(b,a\ mod\ b)$

对于任意自然数$a$,正整数$m$,满足$a \ mod\ m=a-m\left \lfloor \frac{a}{m} \right \rfloor$

裴蜀定理(贝祖定理)$ax+by=c$有解,当且仅当$c|gcd(a,b)$

特殊情况

对于 $ax+by=gcd(a,b)$ ,当$b=0$时,令$x=1,y=0$即可得到一组解。

一般情况

考略递归计算,假设已经算出了$(b \ mod \ a)$的一组解$(x_0,y_0)$,满足$(b \ mod \ a) x_0+ay_0=gcd(a,b)$

\$\$(b-a\left \lfloor \frac{b}{a} \right \rfloor)x_0+ay_0=gcd(a,b)\$\$

$$a(y_0-\left \lfloor \frac{b}{a} \right \rfloor x_0)+bx_0=gcd(a,b)$$

交换$x_0$与$y_0$

$$a(x_0-\left \lfloor \frac{b}{a} \right \rfloor y_0)+by_0=gcd(a,b)$$

$$x=x_0-y_0\left \lfloor \frac{b}{a} \right \rfloor$$

$$y=y_0$$

代码

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

通过$c|gcd(a,b)$,判断是否有解,在有解的情况下:

设我们求出$ax_0+by_0=gcd(a,b)$的一组解。

因为$c|gcd(a,b)$,令$c=gcd(a,b)*k$

$$ax+by=c$$

$$ax+by=gcd(a,b)*k$$

$$a(x/k)+b(y/k)=gcd(a,b)$$

$$x=x_0 \times k ,y=y_0 \times k$$

$$x=x_0 \times (c/gcd(a,b)) ,y=y_0 \times (c/gcd(a,b))$$

求最小正整数解

显然求得的解可能为负数,可是许多题目要求的是正整数解。

求最小整数解,即把$x_0$减少到不能减少为止。

$$ax+by=c$$

$$a\times x_0 \times (c/gcd(a,b))+b\times y_0 \times (c/gcd(a,b))=c$$

当$x_0$减小$t_0$,$y_0$增加了$t_1$,那么:

$$x=x_0 \times (c/gcd(a,b))-(a*c/gcd(a,b)) \times t_1 $$

$$y=y_0 \times (c/gcd(a,b))+(a*c/gcd(a,b)) \times t_0$$

$$ \frac{t_0}{t_1} \ = \frac{b/gcd(a,b)}{a/gcd(a,b)} $$

$$ \frac{t_0}{t_1} \ = \frac{b}{a} $$

那么我们让$x_0$每次减少$b/gcd(a,b)$直到$x_0-i \times x \ge 0 \ And \ x_0-(i+1) \times x<0$即可,其中$i$是减去$x$的次数。

注意$b/gcd(a,b)$可能是负数,总结可得通解公式:

$$x_{min}=(x_0 \ mod \ b/gcd(a,b) + b/gcd(a,b)) \ mod \ b/gcd(a,b)$$

$$y_{min}=(c – a*x_0)/ b$$

在$x$或$y$是负数的时候,需要把$x$与$y$一起变为相反数。

完毕。

例题

洛谷P1082 同余方程

洛谷P1516 青蛙的约会

© 2019 ylxmf2005
转载请联系作者

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据