关于扩展欧几里得算法的自我认识

前景提要：

由于自己数学太过于垃圾，一直没填坑，弄得很迷。。。
然后又不想管。。。
直到集训时，又讲到，qwq。

结束

1. 既然是扩展的欧几里得算法，那么TA也基于欧几里得算法：

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

2. 扩欧是怎样的呢？
   先了解下贝祖定理（裴蜀定理） 吧
   $a、b \in Z$ ，则有 $x,y \in Z$,使得 $ax+by=gcd(a,b)$成立
   这样便有了扩欧的前提。

• 关于 贝祖定理（裴蜀定理） 的小扩展：
  显然: $ax+by=1,那么a与b互质$
• 同理：推广到n个数也成立，这不过是 $gcd(a1,a2,a3...an)$的

扩展欧几里得算法，对于 $ax+by=c$ ( $gcd(a,b)|c \in Z$)，即可以求出gcd(a,b),还可以求出x,y,的一组特解
(PS:对于要求任意解的话：推荐博客)

3. 算法流程(也就是如何做到的)：
   由于 $gcd(a,b)|c \in Z$，不妨设： $c=gcd(a,b)$的情形;
   那么就存在一组特解： $a'=gcd(a,b),b'=0$时， $x=1,y=0,使得：a'x+b'y=gcd(a,b);$

那么就有了两个方程：(PS：默认 $c=gcd(a,b)$的情况)

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

$a'x+b'y=gcd(a,b)$，其中 $a'=gcd(a,b),b'=0,x=1,y=0$;

这样得话，那么对于第二个方程，是不是已经得到解？

那么是不是意味着，若：a’=a,b’=b的话，由当前的x=1，y=0，推出第一个方程的解（这就是为啥说是特解的原因）

考虑到欧几里得算法，TA是不是也是在最后b=0时，a=gcd(a,b);

核心：在欧几里得算法求gcd时，从下推上来，得到当前a,b下的一组（特）解。

4. 证明（如何做到推的？）：
   由于 $gcd(a,b)=gcd(b,a\mod b)$,此处得到了一个相邻态的式子。
   显然： $ax+by=bx+(a\mod b)*y$(此处x，y不一定相等，只表示变量)
   //不理解的话，建议手写两原式子，实践是检验真理的唯一方式;
   已知： $a\mod b=a-\lfloor \frac{a}{b}\rfloor*b$
   那么:
   $bx+(a\mod b)y$
   $=bx+(a-\lfloor \frac{a}{b}\rfloor*b)y$
   $=ay+b(x-\lfloor \frac{a}{b}\rfloor*y)$
   好了，大功告成。
   why？
   这里的式子得x,y,其实为 $bx+(a\mod b)*y$所对应的x,y;
   并且：我们可以认为 $y'=x-\lfloor \frac{a}{b}\rfloor*y$, $x'=y$;
   而a,b，对于 $ax+by$，就是其a，b，只不过位置变了；

综上证明：得到了，相邻类比式的转移，也就得到了核心

Code：
Fir:

当然这里的是默认c=gcd(a,b)的;
int exgcd(int a,int b,int &x,int &y){//这种写法易理解
    if(b==0){
        x=1;y=0;
        return a;	//到达边界开始向上一层返回
    }
    int res=exgcd(b,a%b,x,y);
    int t=y;	//把x,y变成上一层的
    y=x-(a/b)*y;
    x=t;
    return res;	//得到a,b的gcd
}

Sec：

void exgcd(int a,int b,int& x,int& y,int c){
	if(b==0){
		x=c/a,y=0;
		return;
	}
	exgcd(b,a%b,y,x,c);//注意到，这里传递是y,x与上面不同，其实为了不需要再交换x,y
	y-=x*(a/b);
}

后记：

1. 就exgcd练手的话，NOIP 提高组 2012 同余方程，就好了。
2. 逆元，luogu模板题吧。
3. 就是在递归过程中：我们可以求出每层的x，y特解，有的题就会需要，但一般不会让你看出来。（我也记不到，遇见过。qwq）

PS:写的有可能不详细，重在理解吧。emmm…

转载：https://blog.csdn.net/Mosher_muyx/article/details/102156294