扩展欧几里得算法公式快速推导

标签：yb right gcd 推导 int 欧几里得 xa 算法 left

主要是写在这里供自己以后复习查阅所用。

---

求特解

由辗转相除法（欧几里得算法）可得 \(\gcd(a,b)=\gcd(b,a \bmod b)\)

由裴蜀定理，存在 \(x,y\) 使得 \(xa+yb=\gcd(a,b)\)，存在 \(x',y'\) 使得 \(x'b+y'(a \bmod b)=\gcd(b,a \bmod b)\)

所以 \(xa+yb = x'b+y'(a \bmod b)\)

又因为 \(a \bmod b\) 可以写成 \(a - \left\lfloor \dfrac{a}{b} \right\rfloor \times b\)

所以 \(xa+yb = x'b + y' \left( a - \left\lfloor \dfrac{a}{b} \right\rfloor \times b \right)\)

转化右式，\(xa+yb = y'a + \left( x'- \left\lfloor \dfrac{a}{b} \right\rfloor \times y' \right) b\)

这样，左右式就变成了同一个形式，在每次进行辗转相除返回时时令：

\[\left\{ \begin{aligned} x&=y'\\ y&=x'- \left\lfloor \dfrac{a}{b} \right\rfloor \times y' \end{aligned} \right. \]

其中 \(x',y'\) 分别表示后面递归返回的 \(x,y\)。

当 \(b=0\) 时，因为 \(a+b=a=\gcd(a,0)=\gcd(a,b)\)，所以此时 \(x=1,y=1\)。

模板代码：

int exgcd(int a,int b,int &x,int &y)
{
	if(b)
	{
		int res=exgcd(b,a%b,x,y);
		int x_=x;
		x=y,y=(x_-(a/b)*y);
		return res;
	}
	else
	{
		x=1,y=1;
		return a;
	}
}

求通解

解不定方程 \(xa+yb=c\)

设 \(d=\gcd(a,b)\)

标签：yb,right,gcd,推导,int,欧几里得,xa,算法,left
From： https://www.cnblogs.com/jerrycyx/p/18503201