解二元一次不定方程

ax+by=cax+by=c

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

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

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

ax+byax+by

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

=gcd⁡(b,amod  b)=\gcd(b,a\mod \quad b)

=bx′+(amod  b)y′=bx'+(a\mod \quad b)y'

…\ldots

=1=1

(a⊥b)(a\bot b)

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

看两层间关系：

ax+byax+by

=bx′+(amod  b)y′=bx'+(a\mod \quad b)y'

=ay′+b(x′−⌊ab⌋y′)=ay' +b(x'-\lfloor {a \over b} \rfloor y')

由此可以看出：

{x=y′y=x′−⌊ab⌋y′\left\{ \begin{array}{c}x=y'\\y=x'- \lfloor {a \over b} \rfloor y'\\\end{array}\right.

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

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;
}

时间复杂度Θ(log⁡n)\Theta(\log n)

解同余方程

ax≡b(modm)ax\equiv b\pmod m

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

ax=b−myax=b-my

移项得

ax+my=bax+my=b

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