C语言程序扩展欧几里得算法

发布时间:2021-03-24 20:21 作者:独孤剑 阅读:170

给定两个正整数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;
    }
}


作者最新文章
如何设置 robots.txt 只允许抓取首页,不允许抓取其他页面
html table 表格样式
html table 设置表格背景图片,背景色
css, js 引用文件禁止缓存的方法
html 页面禁止缓存