解二元一次不定方程

$$
ax+by=c
$$

有解的条件： $ \gcd(a,b)\mid c$
(若 $\gcd(a,b)$ 与 $c$ 互质或大于则无法配出，因为 $a$ 与 $b$ 能配出的数为 $\gcd(a,b)$ 的倍数)

对原式两边同除$\gcd(a,b)$，
得到 $a’x+b’y=c’$ 此时 $a’\bot b’$ ，
如此可用 $exgcd$ 来求 $a’x+b’y=1$ 的解，进而对得到的答案分别乘以 $c’$ 即可。

求解可在求解 $\gcd$ 的过程中实现，
先将上式变到未知 $\gcd(a,b)$ 前的 $ax+by=\gcd(a,b)$
代入辗转相除过程：

$$
ax+by
$$

$$
=\gcd(a,b)
$$

$$
=\gcd(b,a\mod \quad b)
$$

$$
=bx’+(a\mod \quad b)y’
$$

$$
\ldots
$$

$$
=1
$$

$$
(a\bot b)
$$

$$
\left{\begin{array}{c}x_n=1\y_n=0\end{array}\right.
$$

看两层间关系：

$$
ax+by
$$

$$
=bx’+(a\mod \quad b)y’
$$

$$
=ay’ +b(x’-\lfloor {a \over b} \rfloor y’)
$$

由此可以看出：

$$
\left{ \begin{array}{c}x=y’\y=x’- \lfloor {a \over b} \rfloor y’\\end{array}\right.
$$

那么我们就可以用最后那一组确定的特解不断向前代直到得到 $ax+by=\gcd(a,b)$ 的解
最后附上一份 $exgcd$ 的代码

1
2
3
4
5
6
7
8
9
#define ll long long
ll exgcd(ll a,ll b){
	if(b==0)return a;
	ll res=gcd(b,a%b);
	ll x1=x,y1=y;
	x=y1;
	y=x1-a/b*y1;
	return res;
}

时间复杂度$\Theta(\log n)$

解同余方程

$$
ax\equiv b\pmod m
$$

考虑先把他转换成普通的方程：

$$
ax=b-my
$$

移项得

$$
ax+my=b
$$

之后便可按解二元一次不定方程的步骤来求解