gcd&exgcd【数学向】

Posted on | In |
Words count in article: 651 | Reading time ≈ 2

最近笔者这个蒟蒻学习了扩欧，但是我并不懂得gcd，于是奋发图强，终于，我大概明白了吧

gcd

于是我们从朴素的gcd开始，这是一个求最大公约数的算法，最初由古希腊数学家欧几里得提出，因此得名为欧几里得算法。

下面是正文：

已知$a,b$，求$a,b$的最大公约数。

我们知道，gcd的基础是这个式子：gcd(a,b)=gcd(b,a%b)，那么怎么证呢？

对于$a,b$，我们假设$a=kb+r$则r=a%b，再假设d是(a,b)的公约数，则有$d|a$，$d|b$（“$|$”，意为整除），我们可以再假设$a=q_1d$，$b=q_2d$，又$a=kb+r$，则可知$r=(q_1-q_2)d$，则有$d|r$，则d为(b,a%b)的公约数。

那么反过来，假设$d$为(b,a%b)的公约数，同样假设$a=kb+r$，则r=a%b，那么有$d|b$，$d|r$，继续假设$b=q_1d$，$r=q_2d$，则$a=(kq_1+q_2)d$，可知$d|a$,那么d也为(a,b)的公约数。

可知(a,b)，(b,a%b)的公约数都是相等的，所以其最大公约数也必然相等，那么d是(a,b)的最大公约数为d是(b,a%b)的最大公约数的充要条件，也就是说gcd(a,b)=gcd(b,a%b)，得证。

那么代码就很简单了

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

exgcd

这是让我们求$ax+by=gcd(a,b)$的解的过程

我们知道，gcd是一个靠递归实现的过程，其实exgcd也是一样的东西。那么边界在哪里呢？

毫无疑问，我们知道当$b=0$时，$gcd(a,b)=a$，则必有一组解为$x=1$，$y=0$，那么问题就简单了，只要不断的递归，直到出现$b=0$为止。

那么再怎么反推回去呢？别急，我们来好好分析一下。

还是假设

设$x_1a+y_1b=gcd(a,b)$，$x_2b+y_2(a$%$b)=gcd(b,a$%$b)$

根据上文我们知道$gcd(a,b)=gcd(b,a$%$b)$

所以我们有$x_1a+y_1b=x_2b+y_2(a$%$b)$

所以我们可以写成$x_1a+y_1b=x_2b+y_2(a-[a/b]*b)$

进一步写成$x_1a+y_1b=x_2b+y_2a-y_2[a/b]*b$

在合并一下同类项$x_1a+y_1b=y_2a+(x_2-y_2[a/b])b$

那么比较一下可得$x_1=y_2$，$y_1=x_2-y_2[a/b]$

【注】此处“$[$”、“$]$”意为对$a/b$的下取整。

然后就可以写出代码了：

1
2
3
4
5
6
7
8
9
10
11
inline int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

0%