Chinaunix首页 | 论坛 | 博客
  • 博客访问: 610801
  • 博文数量: 54
  • 博客积分: 3812
  • 博客等级: 上校
  • 技术积分: 992
  • 用 户 组: 普通用户
  • 注册时间: 2007-04-16 20:53
文章分类

全部博文(54)

文章存档

2010年(10)

2009年(24)

2008年(20)

分类: C/C++

2009-03-14 16:42:31

    扩展的欧几里得算法:
    给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得a*m + b*n = d。
 
算法代码如下所示:
 

#include <stdio.h>

int main()
{
    int m, n, a, b, c, d, t;
    int ap, bp;
    int q, r;

    scanf("%d %d", &m, &n);

    ap = b = 1;
    a = bp = 0;
    c = m;
    d = n;

    while (d != 0)
    {
         q = c / d;
         r = c % d;

        c = d;
        d = r;
        
        t = ap;
        ap = a;
        a = t - q * a;
        t = bp;
        bp = b;
        b = t - q * b;
    }

    printf("(%d) * %d + (%d) * %d = %d\n", ap, m, bp, n, c);

    return 0;
}

阅读(1405) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~