数论进阶 

扩展欧几里得算法

裴蜀定理（Bézout's identity）

\(1\) ：对于任意整数 \(a\)，\(b\) ，存在一对整数 \(x\) ，\(y\) ，满足 \(ax+by=GCD(a,b)\) 。

2：对于任意整数 \(a\)，\(b\) ，二元一次不定方程 \(ax+by=c\) 有整数解 \((x,y)\) 当且仅当 \(GCD(a,b)|c\) 。

扩展欧几里得算法（Extended Euclidean algorithm）

首先，我们来回顾一下欧几里得算法：

void gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

扩展欧几里得算法是用于在已知 \(a\)，\(b\) 的情况下求一组解 \(x\)，\(y\) ，使他们之间满足：\(ax+by=GCD(a,b)=d\)。(GCD即最大公约数)。我们要计算的是 \(a\) 和 \(b\) 的最大公约数，并求出 \(x\) 和 \(y\) 使得 \(ax+by=d\)。

此时，我们已经计算出了下一个状态：\(b\) 和 \((a\%b)\) 的最大公约数，并求出了一组 \(x_1,y_1\) 使得：\(bx_1+(a\%b)y_1=d\) 。而相邻状态之间的关系是怎样的呢？

我们知道：\(a\%b=a-\lfloor{a \over b} \rfloor *b\) ，所以有：

\[\begin{align} d&=b * x_1 +[a-\lfloor {a\over b} \rfloor *b]*y_1\\ &=b*x_1+a*y_1-\lfloor{a\over b}\rfloor * b * y_1\\ &=a*y_1+b*(x_1-\lfloor {a\over b} \rfloor * y_1)\\ \end{align} \]

所以：\(x=y_1,y=x_1-\lfloor{a\over b}\rfloor *y_1\) 。

特别的：在欧几里得算法执行到最后一步，即 \(b=0\) 时，我们可以得到一对整数 \(x=1,y=0\) ，使得 \(a*1 + 0*0=GCD(a,0)\) 。

由此便可以写出扩展欧几里得的模板(exGCD)，代码如下：

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if (b==0) {
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return d;
}

未完待续......