这篇文章介绍了扩展欧几里得算法的实现代码，有需要的朋友可以参考一下
给定两个正整数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);
来源gao@dai!ma.com搞$代^码网
因为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;
}
}
{
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;
}
}
以上就是C语言 扩展欧几里得算法代码的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C语言 扩展欧几里得算法代码
转载请注明原文链接：C语言 扩展欧几里得算法代码
