扩展欧几里得

太容易忘记了写一份放博客备份吧

推导之前

根据裴蜀定理，对于任意整数$a,b$以及它们的最大公约数$d$，一定存在两个整数$x,y$使得$ax+by=d$成立

开始推导吧

推导过程中的除法运算结果均进行向零取整

$$\text{设整数}x',y'\text{满足}bx'+(a\bmod b)y'=gcd(b,a\bmod b)=gcd(a,b)$$

$$\text{则有}bx'+(a-a/b*b)y'=gcd(a,b)$$

$$\Leftrightarrow ay'+b(x'-a/b*y')=gcd(a,b)$$

于是在辗转相除法中，对于当前层递归到的一组$a$和$b$，方程$ax+by=gcd(a,b)$的解为

$$x=y'$$

$$y=x'-a/b*y'$$

递归求解即可

Code

void ex_gcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return;
	}
	int xx,yy;
	ex_gcd(b,a%b,xx,yy);//xx,yy即上文提到的x'，y'
	x=yy;
	y=xx-a/b*yy;
}

Part II

在和神仙@GoldenPotato以及@Maxwei_wzj讨论之后引出了一个问题：
对于同余方程$ax+by=(a,b)$它的一组解为$x_0,y_0$，那么所有方程的通解为$$x=x_0+k*\frac{b}{gcd(a,b)}$$

$$y=y_0-k*\frac{a}{gcd(a,b)}$$

其中$k\in \mathbb{Z}$
当求出一个解$x_0$之后，可以通过以下代码获得最小的$x$（令$d=gcd(a,b)$）

x=x%(b/d);

为什么这样是对的？

以下是@Maxwei_wzj给出的证明过程（转述，非原话）%%%%%%%%

令$d=gcd(a,b)$
将方程的通解代入方程，等价于方程$$a(x_0+p)+b(y_0-q)=d$$

$$\Rightarrow ax_0+ap+by_0-bq=d$$

其中$p,q\in \mathbb{N}^*$

$$\because ax_0+by_0=d$$

$$\therefore ap=bq$$

$$\therefore p=\frac{bq}{a}$$

令$a'=\frac{a}{d},b'=\frac{b}{d}$，则有$$p=\frac{b’q}{a’}$$

$$\because gcd(a',b')=1$$

$$\text{要使}p\in \mathbb{N}^*,\text{则}q=k*a',k\in \mathbb{N}^*$$

$$\text{即}p=k*b'=k*\frac{b}{gcd(a,b)}$$

得证，$y$同理

感觉对同余方程的理解又深入了几分呢