扩展欧几里得学习笔记

扩展欧几里得算法用于求解形如

ax+by=gcd(a,b)

的方程(其中a,b是常量且>=0)
首先如果b=0，则显然有x=1，y=0满足上方程

然后如果b>0的话：
首先我们知道gcd(a,b)=gcd(b,a%b)（欧几里得算法求两数gcd的原理）
设上面那个方程的通解为x0，y0
所以就有

a×x0+b×y0=gcd(a,b)

那么

b×x0+(a%b)×y0=gcd(b,a%b)=gcd(a,b)

这里证明个小结论（神仙都是脑补吧……）
a%b==a-b×[a/b]，其中[]表示取整
设a=k×b+m
a%b==m，a/b==k，那么a-b×[a/b]=a-k×b=m=a%b

然后就有

b×x0+(a%b)×y0=b×x0+(a-b×[a/b])×y0

展开，再整理能得到

a×y0+b×(x0-y0×[a/b])

然后上面一长串式子连等下来可以得到

a×y0+b×(x0-y0×[a/b])=gcd(b,a%b)=gcd(a,b)=ax+by（最后这个=开始的）

观察等式两边得到

x=y0，y=x0-y0×[a/b]

然后就可以根据上面过程开始递归了，注意判下边界（b==0）

从lyd书上抄了个代码过来觉得好像理解得更透彻了一点……
所以说学习要勤抄代码（雾
代码我丢一下

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

扩展欧几里得学习笔记

原文：https://www.cnblogs.com/kma093/p/10087108.html