拓展欧几里得
我们先回忆一下朴素的欧几里得算法(辗转相除法)
$gcd(a,b)=gcd(b,a%b)$
|
|
而拓展欧几里得(exgcd)常用来求$ax+by=gcd(a,b)$的一组解。
ax+by=gcd(a,b)
设$x_1,y_1$满足原方程$ax_1+by_1=gcd(a,b)$
根据欧几里得算法不妨构造这样一个方程:
$x_2,y_2$满足$bx_2+(a;mod;b)y_2=gcd(b,a;mod;b)$
所以可得 $ax_1+by_1=bx_2+(a;mod;b)y_2$
由于$a;mod;b=a-(\lfloor\frac{a}{b}\rfloor\times b)$
代入化简,得$ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$
所以可得$x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$
我们知道欧几里得算法不停辗转相除下去,最终会得到a=gcd(a,b),b=0。
因此我们可以根据这个性质不停的构造如上的方程,最后会得到
$gcd(a,b)x+0\times y=gcd(gcd(a,b),0)$
显然此时x=1,y=0可作为方程的一组解,那么只需将这组解往回迭代上去就可以求得原方程的解了。
|
|
ax+by=c
通过上面的方程求解我们不难得到对一个更加普通的不定方程$ax+by=c$的一组解。
设$x_0,y_0$满足$ax_0+by_0=gcd(a,b)$
将$ax_0+by_0=gcd(a,b)$两边同除gcd(a,b)再同乘c
可得$a\frac{cx_0}{gcd(a,b)}+b\frac{cy_0}{gcd(a,b)}=c$
所以,$x=\frac{c}{gcd(a,b)}x_0,y=\frac{c}{gcd(a,b)}y_0$
同时,我们发现$ax+by=c$存在整数解的充要条件为$c%gcd(a,b)=0$;
那么,如果题目要求我们求出x的最小可行解呢?
可令$t=b/gcd(a,b)$,最小的$x=(x;mod;t+t)mod;t$
我们为了让x最小,那么y要尽可能的大,我们可以将x尽可能分成每份为t,因为$t\times a$可以被b整除,所以这些从x里分出来的可给y,那么剩下的x就最小了。
|
|
线性同余方程
$ax\equiv c(mod;b)$
将上面的$ax+by=c$两边同时mod b,我们发现它就转化为$ax\equiv c(mod;b)$这个式子。
也就是说其实$ax+by=c$与 $ax\equiv c(mod;b)$是等价的,那么我们其实已经知道如何求得线性同余方程的解了。
同时我们也知道线性同余方程有解的充要条件为$c%gcd(a,b)=0$