C语言 扩展欧几里得算法代码
给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得a*m+b*n=d
算法流程
E1.置a'=b=1;a=b'=0;c=m,d=n;
E2.计算d和r,使得c=q*d+r;
E3.若r==0;则退出,当前已有a*m+b*n=d;
E4;c=d;d=r;t=a';a'=a;a=t-q*a;t=b';b'=b;b=t-q*b;返回E2.
证明
对于已有的m和n,假设m>n;如果刨除变量a,b,a',b';算法与欧几里得算法完全一样,为计算最大公约数的算法.
最终要求的为a*m+b*n=d=GCD(m,n);如果改式子成立由欧几里得算法可推出a'*n+b'*(m%n)=GCD(n,m%n);
因为GCD(m,n)=GCD(n,m%n);
所以a*m+b*n=a'*n+b'*(m%n)
=a'*n+b'*(m-(m/n)*n)
=a'*n+b'*m-b'*(m/n)*n
=b'*m+(a'-b'*(m/n))*n
所以a=b';b=a'-b'*(m/n);
可以推出根据a‘、b'可以计算a、b。
代码实现
void EGCD(int m,int n)
{
int a,a1,b,b1,c,d,q,r,t;
a1=b=1,a=b1=0,c=m,d=n;
while(1)
{
q=c/d,r=c%d;
if(r==0)
{
printf("(%d)*%d+(%d)*%d=%d\n",a,m,b,n,d);
return;
}
c=d,d=r,t=a1,a1=a,a=t-q*a,t=b1,b1=b,b=t-q*b;
}
}
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了c++中system("pause")的作用和含义,非常不错,具有参考借鉴价值,需要的朋友参考下吧...2020-04-25
基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍 的相关资料,需要的朋友可以参考下...2016-05-14- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
InterlliJ IDEA2020新建java web项目找不到Static Web的解决
这篇文章主要介绍了InterlliJ IDEA2020新建java web项目找不到Static Web的解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-09-02- 这篇文章主要介绍了C#类中static变量用法,实例分析了static变量使用技巧与相关注意事项,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了基于Ionic3实现选项卡切换并重新加载echarts,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-24
- 这篇文章主要给大家介绍C# winform快捷键设置技巧,涉及到C winform快捷键相关知识,对C winform知识感兴趣的朋友可以参考下本篇文章...2020-06-25
- 这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 最近项目不多忙,于是抽点时间巩固下切换窗口问题,感兴趣的朋友跟着小编一起学习吧...2020-06-25
pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率
今天小编就为大家分享一篇pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-05-02基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化的相关知识,主要对比说明在Bootstrap开发中用到的这些技术要点,对此文感兴趣的朋友一起学习吧...2016-05-14- 这篇文章主要为大家详细介绍了PC蓝牙通信C#代码实现,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-06-25
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要介绍了C#实现带进度条的ListView 的相关资料,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了SpringMVC文件上传原理及实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-07-15
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
基于BootStrap的Metronic框架实现页面链接收藏夹功能按钮移动收藏记录(使用Sortable进行拖动排序)
这篇文章主要介绍了基于BootStrap的Metronic框架实现页面链接收藏夹功能按钮移动收藏记录(使用Sortable进行拖动排序)的相关资料,非常不错,需要的朋友可以参考下...2016-09-01- 这篇文章主要介绍了C#向线程中传递多个参数的解决方法(两种)的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25