扩展欧几里得

扩展欧几里得算法

求 $ax+by=g$ 的一组解，其中 $g=\gcd (a,b)$。

辗转相除递归求解。

假设已经求出 $bx+(a\mathrm{mod}b)y=d$ 的一组解。

$$\begin{gathered} ax+by=b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime } \\ =b{x}^{\prime }+(a-b\times \lfloor \frac{a}{b}\rfloor )y^{\prime } \\ =a{y}^{\prime }+b(x^{\prime }-\lfloor \frac{a}{b}\rfloor y^{\prime }) \end{gathered}$$

则 $x=y^{\prime },y=x^{\prime }-\lfloor \frac{a}{b}\rfloor y^{\prime }$。递归计算即可。$b=0$ 时，由辗转相除得 $a=g$，则 $x=1,y=0$ 显然是一组解。

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

扩欧求逆元

求 $a$ 在模 $p$ 下得逆元，等价于求 $ax\equiv 1(\mathrm{mod}p)$，等价于 $ax+py=1$。$\gcd (a,p)=1$ 时才有解，即 $a$ 有逆元。

裴属定理

我们对问题加以扩展，求解 $ax+by=c$。

裴属定理：方程有解当且仅当 $\gcd (a,b)\mid c$。

若方程有解，则用扩欧求出 $ax+by=g$ 对一组特解后乘以 $\frac{c}{g}$ 即可（由裴属定理得 $\frac{c}{g}$ 为整数）。

再找出特解后，加上 $ax+by=0$ 的解即可得到该不定方程的通解。

$$\begin{gathered} \{\begin{array}{l}x=x_0+\frac{b}{g}t\\ y=y_0-\frac{a}{g}t\end{array} \\ (t\in \mathbb{Z}) \end{gathered}$$

例题

iai 两个闹钟

不妨令 $m>n$。

首先有 $n+ax=m+by$。

等价于 $ax+by=m-n$，$x\ge 0,y\le 0$。

裴属定理判断有无解。

因 $m>n$，$y\le 0$ 时 $x$ 一定 $\ge 0$，而 $x\ge 0$ 时 $y$ 不一定 $\le 0$。

故扩欧找出一组特解后，利用零解找一组 $y\le 0$ 的解。又由题，$y$ 应为最小负数。代码。

青蛙的约会

$n+ax\equiv m+bx(\mathrm{mod}P)$

$(a-b)x\equiv m-n(\mathrm{mod}P)$

采用逆元 / 改写二元不定方程的方式，两者本质相同。