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

参考资料

• 最大公约数 - OI Wiki
• Euclidean algorithm - Wikipedia
• Extended Euclidean algorithm - Wikipedia

题意简述

给定 $1\le a,b,c\le 10^9$，求解不定方程：

$$ax+by=c$$

• 若无整数解，输出 -1；
• 若有正整数解，输出正整数解的数量、$x$ 的最小值、$y$ 的最小值、$x$ 的最大值、$y$ 的最大值；
• 若无正整数解，输出 $x$ 的最小正数值和 $y$ 的最小正数值。

基础知识

一次不定方程

一次不定方程（Linear Diophantine Equation）是形如以下形式的方程：

$$a_1x_1+a_2x_2+\dots+a_nx_n=b$$

其中 $a_i$ 和 $b$ 都是整数，我们会研究 $x_i$ 的整数解。

特别地，当 $n=2$ 时为二元一次不定方程：

$$a_1x_1+a_2x_2=b$$

我们可以调整一下变量名：

$$ax+by=c$$

裴蜀定理

裴蜀定理（Bézout's Lemma）给出了二元一次不定方程 有整数解 的充要条件。

对于整数 $a,b$（不全为 $0$），存在整数 $x,y$ 使得 $ax+by=\gcd(a,b)$。

换句话说，$ax+by=c$ 有整数解当且仅当 $\gcd(a,b)\mid c$。

证明详见：Bézout's identity - Wikipedia

欧几里得算法

欧几里得算法（辗转相除法）可以求两个整数的 最大公约数（Greatest Common Divisor，GCD）。

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

证明：设 $a=kb+c$。若 $d\mid a,b$，则 $d\mid c$；若 $d\mid b,c$，则 $d\mid a$。故 $a,b$ 与 $b,c$ 的公约数集合相同，因此 $\gcd(a,b)=\gcd(b,c)=\gcd(b,a\bmod b)$。

显然 $a\bmod b<b$，因此可以递归求解。特别地，$\gcd(a,0)=a$。

$$\gcd(a,b)= \begin{cases} a & b=0 \\ \gcd(b,a\bmod b) & \text{otherwise} \end{cases}$$

ll Gcd(ll a,ll b)
{
	return !b?a:Gcd(b,a%b);
}

扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm，EXGCD）可以求 $ax+by=\gcd(a,b)$ 的 一组整数解。

$$ax+by=\gcd(a,b)\iff ay+b\left(x-\left\lfloor\frac{a}{b}\right\rfloor y\right)=\gcd(a,b)$$

设一组整数解为 $(x_0,y_0)$：

$$ax_0+by_0=\gcd(a,b)$$ $$bx_1+(a\bmod b)y_1=\gcd(b,a\bmod b)$$

根据欧几里得算法：

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

所以：

$$ax_0+by_0=bx_1+(a\bmod b)y_1$$

又因为：

$$a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\times b$$

所以：

$$ax_0+by_0=bx_1+\left(a-\left\lfloor\frac{a}{b}\right\rfloor\times b\right)y_1$$ $$ax_0+by_0=ay_1+bx_1-\left\lfloor\frac{a}{b}\right\rfloor\times by_1=ay_1+b\left(x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1\right)$$

所以：

$$x_0=y_1,y_0=x_1-\left\lfloor\frac{a}{b}\right\rfloor y_1$$

将 $x_1,y_1$ 不断代入递归求解直至 $\gcd$ 为 $0$ 递归 $x=1,y=0$ 回去求解。

解题思路

我们先用 扩展欧几里得算法 求出最大公约数 $g=\gcd(a,b)$ 和一组整数解 $(x_0,y_0)$。

$$ax_0+by_0=g$$

根据裴蜀定理，当 $c$ 不是 $g$ 的倍数时无解，输出 -1。

将方程两边同时乘以 $\frac{c}{g}$：

$$\frac{c}{g}\cdot ax_0+\frac{c}{g}\cdot by_0=\frac{c}{g}\cdot d=c$$

此时我们令 $x_0\gets\frac{c}{g}\cdot x_0,y_0\gets\frac{c}{g}\cdot y_0$，就得到了原问题的一组解 $(x_0,y_0)$。

每两组解的 $x$ 和 $y$ 分别相差了：

$$d_x=\frac{b}{g},d_y=\frac{a}{g}$$

而所有正整数解分别为：

$$(x_{\min},y_{\max}),(x_{\min}+d_x,y_{\max}-d_y),\dots,(x_{\max},y_{\min})$$

显然 $x_{\min}\in[1,d_x],y_{\min}\in[1,d_y]$，可以通过取模得到：

$$x_{\min}=(x_0-1)\bmod d_x+1,y_{\min}=(y_0-1)\bmod d_y+1$$

当 $x$ 最小时 $y$ 最大，$y$ 最小时 $x$ 最大，因此：

$$x_{\max}=\frac{c-by_{\min}}{a},y_{\max}=\frac{c-ax_{\min}}{b}$$

因此正整数的数量为：

$$n=\frac{x_{\max}-x_{\min}}{d_x}+1=\frac{y_{\max}-y_{\min}}{d_y}+1$$

参考代码

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

using ll=long long;
tuple<ll,ll,ll> exgcd(ll a,ll b)
{
	if(!b)return {a,1,0};
	auto [g,x,y]=exgcd(b,a%b);
	return {g,y,x-a/b*y};
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		auto [g,x,y]=exgcd(a,b);
		if(c%g){cout<<-1<<'\n';continue;}
		x*=c/g;y*=c/g;
		ll dx=b/g,dy=a/g;
		ll x_min=(x%dx+dx-1)%dx+1,y_min=(y%dy+dy-1)%dy+1,x_max=(c-b*y_min)/a,y_max=(c-a*x_min)/b;
		if(y_max>0)cout<<(x_max-x_min)/dx+1<<' '<<x_min<<' '<<y_min<<' '<<x_max<<' '<<y_max<<'\n';
		else cout<<x_min<<' '<<y_min<<'\n';
	}
	return 0;
}