扩展欧几里得算法(exgcd)
扩展欧几里得算法,是用来求形如
\[ax+by=c \]的不定方程的整数解的。
判断是否有整数解
根据裴蜀定理,若 \(gcd(a,b) \mid c\),则一定有整数解,否则一定无解。
证明
设 \(d=gcd(a,b)\),显然有 \(d \mid a,d \mid b\)。由于 \(x,y\) 都是整数,所以 \(d \mid (ax),d \mid (by)\)。
所以如果要让式子成立,\(c\) 必须得是 \(a,b\) 的公约数的倍数才对。
又因为 \(x,y\) 是整数,所以 \(c\) 必须是 \(a,b\) 的最大公约数的倍数才行。
实在看不懂的话感性理解下吧awa
转化
让方程两边同除以 \(gcd(a,b)\),可以得到方程
\[a'x+b'y=c' \]其中
\[a'=a \times \frac{gcd(a,b)}{c},b'=b \times \frac{gcd(a,b)}{c},c'=c \times \frac{gcd(a,b)}{c}=gcd(a,b) \]后面求特解中提到的方程均为转化后的方程,即后面方程中的 \(a\) 就是 \(a'\),\(b\) 就是 \(b'\)
求解
求特解
由欧几里得算法可知,\(gcd(a,b)=gcd(b,a \bmod b)\)
于是,我们可以得到
接下来我们就要根据 \(x',y'\) 来反推 \(x,y\)。
因为 \(gcd(a,b)=gcd(b,a \bmod b)\),所以
我们把右边的式子变形一下:
\[bx'+(a \bmod b)y' \]\[=(a-b\left\lfloor\frac{a}{b}\right\rfloor)y'+bx' \]\[=ay'+bx'-b\left\lfloor\frac{a}{b}\right\rfloor y' \]\[= ay'+b(x'-\left\lfloor\frac{a}{b}\right\rfloor y') \]所以,\(x=y',y=x'-\left\lfloor\frac{a}{b}\right\rfloor y')\)。
于是我们只要向欧几里得算法那样递归,就能得到一组特解了。
但还有一个问题,就是递归边界。
递归边界显然是 \(b=0\) 的情况,而此时的方程就变为:
所以此时 \(x=1\),\(y\) 是任意整数。
求解过程用代码写出来就是这个亚子:
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;//y可以是任意整数,这里我们让他等于0也可以
return a;
}
const ll m=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return m;
}
但是但是,这求的是
\[ax+by=gcd(a,b) \]的解呀。不是我们要的解。
因为我们在转化时让方程两边都除以 \(\frac{c}{gcd(a,b)}\),所以现在要乘回来:
求通解
这里我们设之前求出来的通解为 \(x_0,y_0\)。
设 \(d=gcd(a,b)\)
则通解
\(x=x_0+\frac{b}{d} \times t,y=y0-\frac{a}{d} \times t\)
t是任意整数。
为什么是这样呢?
显然我们需要满足
把 \(x,y\) 拆开来:
\[a(x_0+n)+b(y_0-m)=c \]于是就有
\[an-bm=0 \]又因为 \(n,m\) 必须是整数,所以只有上面说的那个可以满足要求了。
求最小正整数解
这里指 \(x\) 是最小正整数。
当我们求出一组特解后,最小正整数解即
上面的式子用的是 C++ 语法。
求最小正整数解惯用手法,这里不再累述。