二元一次不定方程（exgcd）

前置知识

扩展欧几里得算法（辗转相除法）

对 $\forall a,b \in \mathbb{N^+}$ ，有

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

裴蜀定理

对 $\forall a,b\in \mathbb{N^+}$ ， $\exists x,y\in \mathbb{Z}$ ，使得

$ax+by=\gcd(a,b)$

问题引入

给定不定方程

$ax+by=\gcd(a,b)$

求出 $x,y$ 的一组解。

解法：我们令

by'+(a\bmod b)x'=\gcd(b, a\bmod b)

又因为

a\bmod b=a-\lfloor \dfrac{a}{b} \rfloor b

代入得

ax'+b(y'-\lfloor \dfrac{a}{b} \rfloor x')=\gcd(b,a\bmod b)

由 \gcd(a,b)=\gcd(b, a\bmod b)，得

$\left\{ \begin{aligned} x&=x'\\ y&=y'-\lfloor \dfrac{a}{b} \rfloor x' \end{aligned} \right.$

由于在辗转相除法的最后，必定是 $a'=\gcd(a,b),b'=0$ ，则此时 $x'=1,y'=0$ 。那么我们可以在递归回溯的时候逐层求出所求 $x,y$ ，得到如下代码：

void exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0) {
		x = 1; y = 0;
		return;
	}
	exgcd(b, a % b, y, x);
	y = y - a / b * x;
}

注意 $x,y$ 为传址调用。

现在考虑新的问题：等式右边 $\gcd(a,b)$ 被替换为正整数 $c$ ，求解的数量、 $x,y$ 的最大最小值。

把上文代码求得的 $x,y$ 分别乘上 $\dfrac{c}{\gcd(a,b)}$ 即为方程的一组解。

引理 1： $\gcd(a,b) | c$ 是 $ax+by=c$ 有整数解的充分必要条件。

证明：设 $d=\gcd(a,b)$ ， $a=k_1d$ ， $b=k_2d$ ，则 $k_1x+k_2y=\dfrac{c}{d}$ 。左边是整数，因此 $\dfrac{c}{d}\in \mathbb{Z}$ ，即 $d | c$ ，充分性得证。由 $k_1,k_2$ 互质，所以 $k_1x'+k_2y'=1$ 一定有整数解。由 $\dfrac{c}{d}\in \mathbb{Z}$ ，得原方程的一组解为

$\left\{ \begin{aligned} x&=x'\dfrac{c}{d}\\ y&=y'\dfrac{c}{d} \end{aligned} \right.$

必要性得证。

由此我们得到了判断该方程是否有解的方法。

引理 2：设 $x_0,y_0$ 为 $ax+by=c$ 的解，那么所有的解都可表示为

$\left\{ \begin{aligned} x&=x_0+k_2t\\ y&=y_0-k_1t (t\in \mathbb{Z}) \end{aligned} \right.$

把 $x,y$ 代入方程，容易验证。

上式变换后，可知当

$\lceil \dfrac{-x_0+1}{k_2} \rceil \le t \le \lfloor \dfrac{y_0-1}{k_1} \rfloor$

时， $x,y$ 均为正整数。

若 $\lceil \dfrac{-x_0+1}{k_2} \rceil > \lfloor \dfrac{y_0-1}{k_1} \rfloor$ ，则原不定方程无正整数解。

显然 $x$ 越大， $y$ 越小，反之亦然。且正整数解的个数为 $\max\{0,\lfloor \dfrac{y_0-1}{k_1} \rfloor-\lceil \dfrac{-x_0+1}{k_2} \rceil+1\}$ 。

题目应用

到这里我们就可以解决下面这些题了。

【模板】二元一次不定方程 (exgcd)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll T, a, b, c, d, t, cnt;

void exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0) {
		x = 1; y = 0;
		return;
	}
	exgcd(b, a % b, y, x);
	y = y - a / b * x;
}

void solve()
{
	ll x, y, l, r;
	scanf("%lld%lld%lld", &a, &b, &c);
	d = __gcd(a, b);
	if (c % d) {
		printf("-1\n");
		return;
	}
	exgcd(a, b, x, y);
	x *= c / d; y *= c / d;
	a /= d; b /= d;
	l = ceil((1.0 - double(x)) / (double)b);
	r = floor(((double)y - 1.0) / (double)a);
	if (l <= r)
		printf("%lld %lld %lld %lld %lld\n", r - l + 1, x + b * l, y - a * r, (c - b * d * (y - a * r)) / (a * d), (c - a * d * (x + b * l)) / (b * d));
	else
		printf("%lld %lld\n", x + b * l, y - a * r);
}

int main()
{
	scanf("%lld", &T);
	while (T--)	solve();
	return 0;
}

[NOIP2012 提高组] 同余方程

同余方程 ax\equiv c \pmod b 其实就是 $ax+by=c$ 。答案为 $x$ 的最小正整数解。