[原]欧几里得算法+拓展欧几里得算法

1、Euclidean algorithm【辗转相除法】

   古老的求最大公约数（greatest common divisor GCD）的算法

算法思想参见wikipedia：http://en.wikipedia.org/wiki/Euclidean_algorithm

int gcd（int a, int b）
{
    int t;
    if(a < b)
    {
         t = b;
         b = a;
         a = t;
    }
    while(b)
    {
        t = b;
        b = b % a;
        a = t;
    }
   return a;
}

2、 Extended Euclidean algorithm

拓展欧几里得算法能够求 ax + by = gcd(a,b) 中的x, y值。

详细算法思路参见wikipedia：http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

直接用代码表示：

int extgcd(int a, int b, int& x, int &y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a / b) * x;
	}
	else{
		x = 1; y = 0;
	}
	return d;
}

作者：u011652573 发表于2014-3-26 9:09:01 原文链接

阅读：36 评论：0 查看评论