算法学习笔记-exgcd

前言：

\(\operatorname {exgcd}\)，顾名思义，是 \(\gcd\) 的一种扩展。\(\gcd\) 是求最大公因数，所用到的是辗转相除法，基于 \(\gcd(a,b)=\gcd(b,a\mod b) (a>b)\) 的原理，在学习 \(\operatorname{exgcd}\) 前，请确保已掌握 \(\gcd\) ,并懂得一点数学归纳法。如果您已掌握这些前置知识，请开始学习。

例题：

先看这样一道题，给定整数 \(a,b\) ，求 \(x,y\) 使得 \(ax+by=1\)。

性质：

性质1：

这显然是一道数学题（废话），考虑将原式根据乘法分配律转换为 \(\gcd(a,b)\times (\frac{a}{\gcd(a,b)}x+\frac{b}{\gcd(a,b)}y)=1\)。而如果两个整数乘积为 \(1\)，则他们一定为 \(1\)，因此 \(\gcd(a,b)=1\) ,换句话说，\(a,b\) 互质。

综上所述，我们得出性质，若原方程有解，当且仅当 \(a,b\) 互质。

性质2：

这个性质就比较简单，它实际上是类似于递归边界的东西，并不需要怎么推导。考虑当 \(a=1,b=0\) ,原方程有一组解为 \(x=1,y=0\)。

推导：

先看原式：\(ax+by=1\)。
设 \(m = a\mod b\)，\(k=\frac{a}{b}\)，则 \(a=bk+m\)。（其实就是余数和商）。
设有一个和原式一样的方程 \(x'm+y'b=1\)；

根据 \(m\) 的定义，转换为 \(x'(a-kb)+y'b=1\)；

将式子打开，变为 \(x'a-x'kb+y'b=1\)；

合并同类项，变为 \(x'a-(y'-kx')b=1\)；

可以发现一个神奇的事情，转化后的方程与原方程本质是一样的！唯一变化的只有 \(x\) 与 \(y\) 的值。也就是说，若 \(x'（a \mod b）+y'b=1\) 有解，那么 \(ax+by=1\) 也一定有解。而且这个解就是 \(x=x'\), \(y=y'-kx'\)（将所推方程带入）。而根据 \(\gcd\) 的写法，两个互质的数到递归边界时一定是 \(a=1,b=0\)。因为 \(a=1,b=0\) 的情况是有解的，所以 \(\gcd(a,b)=1\) 也是有解的，这也进一步证明了上面的性质。

如果你到这里都听懂了，那么下面的问题就很简单了，只需将 \(x,y\) 代入下面推出来的式子即可。

结论：

通过以上推导，可以得出：

1. 原方程有解当且仅当 \(gcd(a,b)==1\)。
2. 原方程解为 \(y = \begin{cases} x=1，y=0 & a=1,b=0 \\ x=x'，y=y'-kx (x'a \mod b +y'b = 1, k = \frac{a}{b}) & otherwise \\ \end{cases} \)

实现：

\(\operatorname{exgcd}\) 模版见下（递归）：

void exgcd(int a, int b, int &x, int &y)
{
	if(a == 1 && b == 0)//边界 
	{
		x = 1, y = 0;
		return ;
	}
	exgcd(b, a % b, y, x);
	//这里之所以要交换x和y的位置，是因为b与a%b交换了，根据公式要把x,y也换过去 
	y = a / b * x;//按照公式赋值，由于是引用，所以x的值已经更改了。 
}

总结：

第一次学 \(\operatorname{exgcd}\) 时，刚开始看到结论十分蒙，等到搞清楚证明时觉得这个证明妙不可言。笔者认为，学习 \(\operatorname{exgcd}\) 应不仅只会背代码，更要明白证明的过程，最好自己手推一遍。因为证明不仅是解决之后的许多与 \(\operatorname{exgcd}\) 的题有关，更能扩展思维，对数轮有很大帮助。

鉴于笔者也是蒟蒻，文中给出的部分推导过程与表述可能不严谨，欢迎大佬在评论区指出。