扩展欧几里得是用来在 已知 $a, b$ 求解一组 $x, y$,使它们满足贝祖等式:$ax+by=gcd\left(a,b\right)$(解一定存在,根据数论中的相关定理)。扩展欧几里得常用在求解模线性方程及方程组中。
贝祖定理:设 $a,b$ 是不全为零的整数,则存在整数 $x,y$,使得 $ax+by=gcd\left(a,b\right)$。

1
2
3
4
5
6
7
8
9
10
11
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int q = exgcd(b, a % b, y, x);
y -= a / b * x;
return q;
}

关于最小正整数解的问题,是使 $x,y$ 中某一个为最小正整数即可,求得某一个的最小正整数值后再根据这个值去计算另一个。
方程的解 $x$ 具有周期 $\frac{b}{gcd\left(a,b\right)}$, $y$ 具有周期 $\frac{a}{gcd\left(a,b\right)}$。解集为
$
\cdots \
x,y \
x+\frac{b}{gcd\left(a,b\right)},y-\frac{a}{gcd\left(a,b\right)} \
x+\frac{2b}{gcd\left(a,b\right)},y-\frac{2a}{gcd\left(a,b\right)} \
x+\frac{3b}{gcd\left(a,b\right)},y-\frac{3a}{gcd\left(a,b\right)} \
\cdots
$
例如,求 $x$ 为最小正整数的解,$x_{min}=(x%\frac{b}{gcd\left(a,b\right)}+\frac{b}{gcd\left(a,b\right)})%\frac{b}{gcd\left(a,b\right)}$,然后根据 $x_{min}$ 值去计算对应的 $y$ 。因为我们对 $\frac{b}{gcd\left(a,b\right)}$ 取余,如果一开始计算出的 $x$ 是负数,就会得出负的结果,不满足要求,所以取余后要再加上 $\frac{b}{gcd\left(a,b\right)}$ ,使它变成正数。如果一开始就是正数,那么一加就不是最小的整数解了,所以再对 $\frac{b}{gcd\left(a,b\right)}$ 取余一次。
同理,$y_{min}=(y%\frac{a}{gcd\left(a,b\right)}+\frac{a}{gcd\left(a,b\right)})%\frac{a}{gcd\left(a,b\right)}$,根据 $y_{min}$ 值去计算对应的 $x​$ 。

应用:
1. 求不定方程(二元一次方程)的最小正整数解
解形如 $ax+by=c$ 的二元一次方程,方程必须有整数解。。。先算出 $c$ 是 $gcd\left(a,b\right)$ 的几倍,然后将扩展欧几里得求出来的 $x$ 和 $y$ 分别乘以这个求出来的倍数,就是答案。
想要求出整数解,原式就必须满足 $gcd\left(a,b\right)\mid c$,否则没有整数解。

1
2
3
4
5
6
7
8
9
10
bool eqa_solve(int &x, int &y, int a, int b, int c)
{
int q = exgcd(a, b, x, y);
if (c % q != 0)
return false;
int tms = c / q;
x *= tms;
y *= tms;
return true;
}

函数返回值为 true 表示方程有整数解,为 false 表示无整数解。
$x,y$ 为整数,关于最小正整数解,将求得的 $x,y$ 按文章开头步骤操作即可。

2. 求乘法逆元
在取余运算中,对加、减、乘、乘方的取余通常满足以下式子:
$(a+b)%p=(a%p+b%p)%p$
$(a−b)%p=(a%p−b%p)%p$
$(a\times b)%p=(a%p\times b%p)%p$
$(a^b)%p=((a%p)^b)%p$
然而除法 $(a\div b)%p\neq (a%p\div b%p)%p$。为了实现除法取余,引入乘法逆元 $c$ , 使 $(a\div b)%p=(a\times c)%p$。
代码要求待求乘法逆元的 $b$ 与 $mod$ 互质,在大多题目中,$mod$ 为质数。

1
2
3
4
5
6
int mod_inverse(int b, int mod)
{
int x, y;
exgcd(b, mod, x, y);
return (mod + x % mod) % mod;
}

参数为 $b$ 和 $mod$,返回值为 $b$ 模 $mod$ 的乘法逆元 $c$ 。
即 $(a\div b)%p=(a\times mod\_inverse(b))%p$,注意若 $mod$ 较大(比如 ACM 常见 1e9+7),数据类型应使用 long long。

3. 解线性同余方程
同余方程 $ax\equiv b\pmod m$ (也就是 $ax%m=b%m$),解出 $x$ 。即求解 $ax+my=b%m$ ($y$ 也是未知数)。
以 $a,m,b%m$ 分别替换不定方程 $ax+by=c$ 中的 $a,b,c$ 求解即可。

1
2
3
4
5
bool congruence_solve(int a, int &x, int b, int m)
{
int y;
return eqa_solve(x, y, a, m, b % m);
}

函数返回值为 true 则 $x$ 为解,为 false 表示此线性同余方程无解。