数论：不定方程整数解 - 算法 - 数论

# 欧几里得算法

又称辗转相除法，迭代求两数 gcd。

由 $(a, b) = (a, ka + b)$ 的性质， $\gcd(a, b) = \gcd(b, a\bmod b)$ 。容易证明这么做的复杂度是 $O(\log n)$ 。

注意： $\gcd(0, a) = a$ 。

# 裴蜀定理

裴蜀定理：设 $(a, b) = d$ ，则对任意整数 $x, y$ ，有 $d|(ax + by)$ 成立；特别地，一定存在 $x, y$ 满足 $ax + by = d$ 。

等价的表述：不定方程 $ax + by = c(a, b, c 为整数)$ 有解的充要条件为 $(a, b)|c$ 。

# P4549 【模板】裴蜀定理

裴蜀定理可以推广到多元方程。

	#include <stdio.h>
	#include <string.h>
	#include <iostream>
	#include <algorithm>
	using namespace std;

	int main() {

	int n; scanf("%d", &n); int a; scanf("%d", &a); int g = a;
	for(int i=2; i<=n; ++i) {
	scanf("%d", &a); if(a == 0) continue;
	if(a < 0) a = -a;
	g = __gcd(g, a);
	}
	printf("%d\n", g);
	return 0;
	}

# 扩展欧几里得（exgcd）

裴蜀定理的推论： $a, b$ 互质等价于 $ax + by = 1$ 有解。

因此，要求不定方程 $ax+by=c$ 的解，只需求 $ax+by=d,d=\gcd(a,b)$ 的解，然后扩倍（乘上 $\frac{c}{d}$ ）即可。

# 求出任意一个解

考虑使用欧几里德算法的思想，令 $a = bq + r$ ，其中 $r = a \bmod b$ ，递归求出 $bx + ry = d$ 的一个解。

设求出 $bx + ry = d$ 的一个解为 $x = x_0, y = y_0$ ，考虑如何把它变形成 $ax + by = d$ 的解。

将 $a = bq + r$ 代入 $ax + by = d$ ，化简得

$b(xq + y) + rx = d$

令

$xq + y = x_0, x = y_0$

上式成立。

故

$x = y_0, y = x_0 - y_0q$

为 $ax + by = d$ 的解。

注意边界情况：当 $b = 0$ 时，必有 $a = d$ ，此时令 $x = 1, y = 0$ 即可。

# 怎么求出所有解？

先用 exgcd 求出任意一个解 $x = x_0, y = y_0$ ，再求出 $ax + by = 0$ 的最小的解

$x = dx = b/(a, b), y = dy = -a/(a, b)$

所有解就是

$x = x_0 + kdx, y = y_0 + kdy,k\in \mathbb{Z}$

# P1082 同余方程

	#include <stdio.h>
	#include <string.h>
	#include <iostream>
	using namespace std;

	typedef long long ll;
	typedef pair<ll, ll> pll;
	ll a, b;
	pll exgcd(ll a, ll b) {
	if(b == 0) return {1,0};
	pll p = exgcd(b, a%b);
	return {p.second, p.first-a/b*p.second};
	}

	int main() {

	scanf("%lld%lld", &a, &b);
	ll x = exgcd(a,b).first;
	while(x < 0) x+=b;
	while(x-b > 0) x-=b;
	printf("%lld\n", x);
	return 0;
	}

# P3951 [NOIP2017 提高组] 小凯的疑惑

方法很多，这里提供一个比较好理解的扩欧做法。

首先已知题目必存在答案，那么设答案为 $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'')$ ，他们都是离水平面（原点）最近的解，所以他们在扩欧通解上是两组相邻的解

则

$\begin{aligned} ans&=k-1\\ &=a(x'-1)+b(y''-1)-1 \\ &=ax'-a+by''-b-1 \\ &=ax'+by'+ab-a-b-1 \\ &=ab-a-b. \end{aligned}$

算法数论