# 扩展欧几里得

求不定 ax+by=cax+by=c 的所有整数解。

# 判断该方程是否有解

裴蜀定理:设 gcd(a,b)=d\gcd(a, b) = d,则对任意整数 x, y,有 d|(ax + by) 成立;
特别地,一定存在 x, y 满足 ax + by = d

等价的表述:不定方程 ax + by = c (a, b, c 为整数) 有解的充要条件为 (a, b)|c
推论:a, b 互质等价于 ax + by = 1 有解

因此只要求出 ax+by=gcd(a,b)ax+by=\gcd(a,b) 的解,然后扩倍(乘上 [c][d]\frac[c][d])即可。

# 求出任意一个解

考虑使用欧几里德算法的思想,令 a = bq + r,其中 r = a mod b;
递归求出 bx + ry = d 的一个解。
设求出 bx + ry = d 的一个解为 x = x0, y = y0,考虑如何把它变形成 ax + by = d 的解。
将 a = bq + r 代入 ax + by = d,化简得 b (xq + y) + rx = d
我们令 xq + y = x0, x = y0,则上式成立
故 x = y0, y = x0 - y0q 为 ax + by = d 的解

注意边界情况:当 b=0b = 0 时,此时 a=gcd(a,b)=da = \gcd(a,b) = d,因此令 x=1,y=0x = 1, y = 0 即可。

# 怎么求 ax+by=dax + by = d 的所有解?

先用 exgcd 求出任意一个解 x = x0, y = y0
再求出 ax + by = 0 的最小的解
x = dx = b/(a, b), y = dy = -a/(a, b)
所有解就是 x = x0 + kdx, y = y0 + kdy, k 取任意整数

# NOIP2017 D1T1 小凯的疑惑

有一个比较好理解的扩欧做法

已知题目必存在答案,那么设 k1k-1 为答案,则 ax+by=kax+by=k 必有一组非负整数解 (x,y)(x,y)

假设 ax+by=k1ax+by=k-1 有非负整数解,那么该式必能化为

a(xx0)+b(yy0)=ka(x-x_0)+b(y-y_0)=k

其中

ax0+by0=1ax_0+by_0=1

注意到,若尽量使该式能够有解,则有两种情况,分别令 x0x_0y0y_0 取其最小非负整数解 xx'yy''(因为一方最小时另一方必为最大情况)

因此为了让原式无解,需保证 xx<0,yy<0x-x'<0, y-y''<0,即 x<x,y<yx<x',y<y''

因为要构造最大非负整数解,所以令 x=x1,y=y1x=x'-1,y=y''-1 所得即为 kk,答案即为 a(x1)+b(y1)1a(x'-1)+b(y''-1)-1

到这就可以结束了,不过其实还能进一步化简

有一个很显然的结论,ax0+by0=1ax_0+by_0=1 是没有非负整数解的

x,yx,y 想象成分别在两个竖直的数轴上,可以发现,对于上面的两组解 (x,y)(x',y')(x,y)(x'',y''),他们都是离水平面(原点)最近的解,所以他们在扩欧通解上是相邻的

y=y+ay''=y'+a,原式

a(x1)+b(y1)1a(x'-1)+b(y''-1)-1

=axa+byb1=ax'-a+by''-b-1

=ax+by+abab1=ax'+by'+ab-a-b-1

=abab.=ab-a-b.

更新于