学习笔记--扩展欧几里得

前言

在noip前就对此算法进行过一些了解，然而noipD1T1压根没想到扩欧，说明我之前学的东西根本不扎实，于是现在跑来补坑

更项减损法&欧几里得算法

先来介绍一个在《九章算术》中出现的更相减损法：

对于任意正整数(a>=b),都有(gcd(a,b)=gcd(b,a-b)=gcd(a,a-b))
证明：

对于a,b任意公约数d,因为(dmid b,d|a),所以(dmid (a-b)),所以a,b的公约数集合与(b,a-b)的公约数集合相同，对于(a,a-b)也同理。

然后就是大名鼎鼎的欧几里得算法：

对于任意正整数$a,b (b e 0) $ 有， (gcd(a,b)=gcd(b,amod b))

进行高精度运算时，可考虑更项减损法代替。

裴蜀定理((Bézout's) (lemma))

对于任意整数(a,b),存在一对整数，满足(ax+by=gcd(a,b))
证明：

我觉的还是《算法竞赛进阶指南》中给出证明更有帮助：

在欧几里得算法最后一步,即(b=0)时，显然有一对整数(x=1,y=0),满足(a*1+b*0=gcd(a,0))

若(b > 0)，则(gcd(a,b)=gcd(b,a mod b))。假

设存在一对整数(x,y),满足(b*x+(a mod b)*y=gcd(b,a mod b))，

因为(bx+(a mod b)y)

(=bx+(a-blfloor a/b floor)y)

(=ay-b(x-lfloor a/b floor y))，

所以令(x'=y,y'=x-lfloor a/b floor y)就能得到(ax'+by'=gcd(a,b))

应用数学归纳法（如果您不知道这是什么，您可以把它想象成一个递推或递归过程），可知此定理成立。

上述证明过程还给出了(x,y)的计算过程，用代码写就是

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

ex_gcd返回(gcd(a,b))，同时求出一组解(x,y)

对于(ax+by=c),它有解当且仅当(gcd(a,b)mid c)

然后，此方程的通解可表示为：

(x=(c/d)*x0+k*(b/d)) ，(y=(c/d)*y0-k*(a/d))

其中(k)取任意整数，(d)为(gcd(a,b)).

这是为什么呢？我辗转于各大博客都无清楚的解释，在我坚韧不拔意志的驱使下，终于在洛谷网课上找到了一个简洁易懂的证明:

证明：

我们先考虑：(ax+by=gcd(a,b))的情况,

显然(a*b+b*(-a)=0) 同时除以(gcd(a,b)),易知这是可行的

所以(a*(b/gcd(a,b))+b*(-a/gcd(a,b))=0)

所以若已知(x0,y0)为一组特解即(a*x0+b*y0=gcd(a,b))，不妨令(x=x0+k*b/gcd(a,b)) ,(y=y0-k*(a/gcd(a,b))),

带入(ax+by)得(a(x0+k*b/gcd(a,b))+b*(y0-k*(a/gcd(a,b))))

(=ax0+by0+k*(a*b/gcd(a,b)-b*a/gcd(a,b)))

(=ax0+by0=gcd(a,b))

然后(ax+by=c)的也很好解决掉了，这里不赘述

学习笔记--扩展欧几里得

前言

相关概念：

更项减损法&欧几里得算法

裴蜀定理((Bézout's) (lemma))

相关