欧几里得算法（辗转相除法）

设gcd(a,b)是计算自然数a和b的最大公约数的函数，a除b得到的商和余数分别为p和q，因为a=b×p+q，所以gcd(b,q)既整除a又整除b，也就是整除gcd(a,b)。反之，因为q=a-b×p，同理可证gcd(a,b)整除gcd(b,q)。因此可以知道gcd(a,b)=gcd(b,a%b)。不断这样操作下去，由于gcd的第二个参数总是不断减小的，最终会得到gcd(a,b)=gcd(c,0)。0和c的最大公约数是c，这样便计算出了a，b的最大公约数为c。

1
2
3
4
5
int gcd(int a, int b){
	if(b == 0)
		return a;
	return gcd(b, a%b);
}

时间复杂度

O(log max(a,b))之内



扩展欧几里得算法

贝祖定理：

对于给定的正整数a，b，方程ax+by=c有解的充要条件为c是gcd（a，b）的整数倍


根据欧几里得算法，当到达递归边界的时候，a_i== gcd(a_0,b_0) , b_i == 0，可以得到一个较为明显的解： a_i * 1 + b_i * 0 = gcd(a_0,b_0) ,即 x_i = 1, y_i = 0。因为递归的特性是由最终状态逐层返回的，现在我们已经知道了最终状态的x_i 和y_i，只需要找出x和y变化的关系式即可。

由欧几里得算法可得：

a * x_0 + b * y_0 = gcd(a ,b )

b * x_1 + (a % b) * y_1 = gcd(a,b)

因为a % b = a - ( a / b) * b（此处”/“为整除）

b * x_1 + a * y_1 - ( a / b) * b * y_1 = gcd(a,b)

a * y_1 + b * ( x_1 - ( a / b) * y_1) = gcd(a,b)

即：x_0 = y_1 , y_0 = (x_1 - a / b) * y_1)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法
{
    if(b==0)
    {
        x=1;y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    int r=exgcd(b,a%b,x,y);
    int temp=y;    //把x y变成上一层的
    y=x-(a/b)*y;
    x=temp;
    return r;     //得到a b的最大公因数
}