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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法•日更•第五十六期】扩展欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含866字，纯文字阅读大概需要2分钟。

内容图文

▎裴蜀定理

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

　　

　　必定有解。

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

▎不定方程

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

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

　　所以问题就是：

　　

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

▎问题解决

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

　　

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

　　

　　的解（x‘，y’）呢？

　　先抛出结论：

　　下面是证明过程：

　　

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

　　

　　的时候很快推出：

　　

　　这样可以层层递归下去，直到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 }

内容总结

以上是互联网集市为您收集整理的【算法•日更•第五十六期】扩展欧几里得算法全部内容，希望文章能够帮你解决【算法•日更•第五十六期】扩展欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---