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

淩亂°似流年 2023-06-03 02:53 96阅读 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. 1 pair<int,int> exgcd(int a,int b)
  2. 2 {
  3. 3         if(b==0) return pair(1,0);
  4. 4         pair<int,int> sum=exgcd(b,a%b);
  5. 5         return pair<int,int>(y,x-a/b*y);
  6. 6 }

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

发表评论

表情：
评论列表 （有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

    相关 扩展欧几里得算法

    poj 1061题目，青蛙的约会。一开始想暴力求解的。但是之前提交过，tle... 今天过来查一下，说是扩展欧几里得算法。我了个去。这么复杂的名字，得是有多深奥。 查了才知

    系统管理员系统管理员/ 0 赞/ 287 阅读

    相关 扩展欧几里得算法

    问题描述： 求解二元一次方程ax+by=c。 问题分析： 上述的二元一次方程可以用同余方程来进行描述：ax≡cmod(b) 两个问题可以进行转换，但是都可以用扩展的欧几

    心已赠人心已赠人/ 0 赞/ 328 阅读