【算法•日更•第五十六期】扩展欧几里得算法

淩亂°似流年 2023-06-03 02:53 49阅读 0赞

▎裴蜀定理

这个定理很简洁，就是关于x，y（都是**整数**）的不定方程在下面的情况下：

![1551435-20190822161424516-1888148910.png][]

**必定**有解。

这只是个前置知识，就不证明了（主要是小编太菜）。

▎不定方程

考虑方程ax+by=c的解的情况：

*  若c=gcd（a，b），那么依照裴蜀定理有解；
 *  若c=k\*gcd（a，b），先两边同除k，就会转化成标准形式，有解；
 *  若c与gcd（a，b）互质，那么无解；

所以问题就是：

![1551435-20190822162031555-1201983645.png][]

如何解决，只要解决了这个问题，所有解的情况就解决了。

▎问题解决

现在我们考虑怎么让这个问题更简单，思考这样一个问题，已知：

![1551435-20190822162201008-623433601.png][]

的解（x，y），那么怎么推出：

![1551435-20190822162256548-568808293.png][]

的解（x‘，y’）呢？

先抛出结论：![1551435-20190822162411255-2092586800.png][]

下面是证明过程：

![1551435-20190822163745392-1302031334.png][]

知道了这个东西之后，我们就可以在算完

![1551435-20190822162201008-623433601.png][]

的时候很快推出：

![1551435-20190822162256548-568808293.png][]

这样可以层层递归下去，直到y=0，那么x=1，y=0的情况下就是a+0=gcd（a，0），此条件成立，那么再回溯回去就可以了。

▎代码实现

感觉像极了辗转相除法。

1 pair<int,int> exgcd(int a,int b)
    2 {
    3         if(b==0) return pair(1,0);
    4         pair<int,int> sum=exgcd(b,a%b);
    5         return pair<int,int>(y,x-a/b*y);
    6 }

转载于:https://www.cnblogs.com/TFLS-gzr/p/11395285.html

[1551435-20190822161424516-1888148910.png]: /images/20230601/0af9d7cccd4241dda5deb3e7665ef33c.png
[1551435-20190822162031555-1201983645.png]: /images/20230601/5bb9829583f245b1bb9fc8837ecb9f66.png
[1551435-20190822162201008-623433601.png]: /images/20230601/4646c8c22f6347cfb0481222a60863bb.png
[1551435-20190822162256548-568808293.png]: /images/20230601/698838be90384a1ca14a5b4321820bdb.png
[1551435-20190822162411255-2092586800.png]: /images/20230601/a3a6a992f055422eb4f8175ab4d118f7.png
[1551435-20190822163745392-1302031334.png]: /images/20230601/bf899640a36a4058a8bd005b505c6b13.png