推式子——拓展欧几里德算法exgcd

标签：lfloor frac gcd int 欧几里德 exgcd rfloor bmod 式子

试求方程 \(ax+by=\gcd(a,b)\) 的一组整数解,其中 \(a\) 和 \(b\) 是给定的数

提前准备好一个式子:辗转相除法

\[\gcd(a,b)=\gcd(b,a \bmod b) \]

同时我们可以注意到， \(\bmod\) 的等价版本:

\[a \bmod b=a-b\lfloor \frac{a}{b}\rfloor \]

开始推式子

首先考虑 \(b=0\) 的情况，因为 \(\gcd(a,0)=a\)，所以此时的一组解我们可以定为 \(x=1,y=0\)

其次开始考虑 \(b\neq 0\) 的情况咯，我们可以转先求 \(bx+(a\bmod b)y=\gcd(b,a\bmod b)\) 的解，求出来 \(x=x_0,y=y_0\)

那么上面的方程式可以化为

\[ax+by=bx_0+(a\bmod b)y_0=bx_0+(a-b\lfloor \frac{a}{b}\rfloor)y_0 \]

进一步提取因式，可得 $$ax+by=ay_0+b(x_0-\lfloor\frac{a}{b}\rfloor y_0) $$

容易发现一组解就是

\[x=y_0,y=x_0-y_0\lfloor\frac{a}{b}\rfloor \]

你要是问我怎么求出 \(x_0\) 和 \(y_0\) 的，我阿只能说

递归阿!

code:

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

标签：lfloor,frac,gcd,int,欧几里德,exgcd,rfloor,bmod,式子
From： https://www.cnblogs.com/exut/p/18316056