# 扩展欧几里得
求不定 的所有整数解。
# 判断该方程是否有解
裴蜀定理:设 ,则对任意整数 x, y,有 d|(ax + by) 成立;
特别地,一定存在 x, y 满足 ax + by = d
等价的表述:不定方程 ax + by = c (a, b, c 为整数) 有解的充要条件为 (a, b)|c
推论:a, b 互质等价于 ax + by = 1 有解
因此只要求出 的解,然后扩倍(乘上 )即可。
# 求出任意一个解
考虑使用欧几里德算法的思想,令 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 的解
注意边界情况:当 时,此时 ,因此令 即可。
# 怎么求 的所有解?
先用 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 小凯的疑惑
有一个比较好理解的扩欧做法
已知题目必存在答案,那么设 为答案,则 必有一组非负整数解
假设 有非负整数解,那么该式必能化为
其中
注意到,若尽量使该式能够有解,则有两种情况,分别令 或 取其最小非负整数解 和 (因为一方最小时另一方必为最大情况)
因此为了让原式无解,需保证 ,即
因为要构造最大非负整数解,所以令 所得即为 ,答案即为 。
到这就可以结束了,不过其实还能进一步化简
有一个很显然的结论, 是没有非负整数解的
把 想象成分别在两个竖直的数轴上,可以发现,对于上面的两组解 、,他们都是离水平面(原点)最近的解,所以他们在扩欧通解上是相邻的
则 ,原式