扩展欧几里德算法，直线上的点

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了扩展欧几里德算法，直线上的点，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含657字，纯文字阅读大概需要1分钟。

内容图文

课本上关于这一节讲得不是很清楚

部分内容参考自：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

扩展欧几里德算法

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

扩展欧几里德算法的应用主要有以下三方面：

（1）求解不定方程；

（2）求解模线性方程（线性同余方程）；

（3）求解模的逆元；

 

（1）：

　　设a,b,c为任意整数，g=gcd（a，b），方程ax+by=g的一组解为（x0，y0），则当c为g的倍数时，ax+by=c的一组解为（p0，q0）=（x0*c/g,y0*c/g），方程的其他解为（pi，qi）=（p0 + b/g * t，q0-a/g*t）其中t为任意值；当c不为g的倍数时，不存在解

                //
                算法,解方程ax+by=gcd(a,b),其中d=gcd(a,b),x,y初始值任意即可 
                void MEuclid(int a,int b,int &d,int &x,int &y)
{
 if(b==0){d=a;x=1;y=0;return;}
 else     {MEuclid(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}

View Code

 

原文：http://www.cnblogs.com/bingolibing/p/4492180.html

内容总结

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

内容备注

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

内容手机端

---