数论：不定方程整数解

# 扩展欧几里得

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

# 判断该方程是否有解

裴蜀定理：设 $\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)$ 的解，然后扩倍（乘上 $\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 = 0$ 时，此时 $a = \gcd(a,b) = d$，因此令 $x = 1, y = 0$ 即可。

# 怎么求 $ax + 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 小凯的疑惑

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

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

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

$$a(x-x_0)+b(y-y_0)=k$$

其中

$$ax_0+by_0=1$$

注意到，若尽量使该式能够有解，则有两种情况，分别令 $x_0$ 或 $y_0$ 取其最小非负整数解 $x'$ 和 $y''$（因为一方最小时另一方必为最大情况）

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

因为要构造最大非负整数解，所以令 $x=x'-1,y=y''-1$ 所得即为 $k$，答案即为 $a(x'-1)+b(y''-1)-1$。

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

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

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

则 $y''=y'+a$，原式

$$a(x'-1)+b(y''-1)-1$$

$$=ax'-a+by''-b-1$$

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

$$=ab-a-b.$$