扩展的欧几里得算法

    扩展的欧几里得算法：

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