专栏文章

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

LLOVE118
P5656题解参与者 4已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mio6ul86
此快照首次捕获于
2025/12/02 14:19
3 个月前
此快照最后确认于
2025/12/02 14:19
3 个月前
查看原文

解析

由裴蜀定理可知一定有一组 x,yx,y 使 ax+by=ax + by = gcd(a,b)(a, b) 成立，而对于 ax+by=cax + by = c，cc 必须是 gcd(a,b)(a, b) 的倍数该方程才会有解，否则无解（裴蜀定理还不会的点这里裴蜀定理）。
恭喜你已经会了第一步，成功的掌握了前置知识，现在我们继续研究，先从求解 ax+by=ax + by = gcd(a,b)(a, b) 入手吧！
相信聪明的你一定会辗转相除求 gcd 吧，我们来模拟一下这个过程，假设现在有 220220 和 150150 两个数：
第一轮：220 170220 ~170 较小数不为零，继续 gcd(170,220 mod 170)(170, 220 \bmod 170)
第二轮：170 50170 ~50 继续 gcd(50,170 mod 50)(50, 170 \bmod 50)
第三轮：50 2050 ~20 继续 gcd(20,50 mod 20)(20, 50 \bmod 20)
第四轮：20 1020 ~10 继续gcd(10,20 mod 10)(10, 20 \bmod 10)
第五轮：10 010 ~0 较小数为零了，返回。
我们回头再看每一轮的操作，假设现在的第一个数为 x0x_0，第二个数为 y0y_0，现在即将生成下一轮的两个数 x1,y1x_1,y_1。
x1=y0x_1 = y_0 不用多说，y1=x0 mod y0y_1 = x_0 \bmod y_0 怎么办呢？
好吧，其实 y1=x0−y0×⌊x0y0⌋y_1 = x_0 - y_0 \times \lfloor\frac{x_0}{y_0}\rfloor。
因此，我们可以不断用 xx 去代换 x′x'，用 yy 取代换 y′y'，最后 gcd(a,b)(a, b) 就可以用 ax+byax + by 来表示了，方程得解。
大功告成，现在我们已经成功得到了一组解 x0x_0 和 y0y_0，回到 ax+by=cax + by = c 中，则 x=x0×cgcd⁡(a,b)x = x_0 \times \frac{c } {\gcd(a, b)}，y=y0×cgcd⁡(a,b)y = y_0 \times \frac{c } {\gcd(a, b)}，然后将等式两边同时除以 gcd(a,b)(a,b)。 得到a′x+b′y=c′a'x + b'y = c'
现在假设存在另外一组 x′x' 和 y′y' 使等式成立，则我们可以这样表示 x′x' 和 y′y' ：
x′=x+kb′y′=y−ka′x' = x + kb'\\ y' = y - ka'
考虑 xminx_{min}，则 x+kb′≥1x + kb' \ge 1，可得 k≥(1−x)/b′k \ge (1 - x) / b'，那么 xmin=x+b′⋅⌈(1−x)b⌉x_{min} = x + b' \cdot \lceil\frac{(1 - x)}{b}\rceil，yminy_{min} 同理可得。
再考虑 xmaxx_{max}，因为 xx 和 yy 肯定是你增我减才能使等式依然成立，则 yminy_{min} 时取到 xmaxx_{max}，xminx_{min} 时取到 xmaxx_{max}。
那么解的个数是多少呢？ 因为 yy 最大值与最小值之间每 bb 个数就有一个解，所以个数为 ymax−ymina+1\frac{y_{max} - y_{min}} {a}+ 1 个。
最后一步，判定是否无正整数解，不难发现，若 xx 取最小值时，ymax≤0y_{max} \le 0 那么 ymaxy_{max} 肯定无法更大了，因此可以判定为无解。
最后代码奉上：
CPP
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

int aa, bb, cc, ans = 0, jx = 0, jy = 0;
int x, y = 0;
void exgcd(int a, int b, int xa, int ya, int xb, int yb){//求一组特殊解 
	if(b == 0){
		ans = a;
		jx = -xa;
		jy = -ya;
		return ;
	}
	else{
		int k = a / b;
		exgcd(b, a % b, xb, yb, xa - k * xb, ya - k * yb);
	}
}
signed main()
{
	int T = 0;
	cin >> T;
	for(int t = 1; t <= T; t++){
		cin >> aa >> bb >> cc;
		exgcd(aa, bb, -1, 0, 0, -1);
		if(cc % ans != 0){//判定无解 
			cout << -1 << endl;
			continue;
		}
		aa = aa / ans;//化为最简式 
		bb = bb / ans;
		cc = cc / ans;
		jx = jx * cc;
		jy = jy * cc;
		double ka = ceil((1.0 - jx) / bb);
		int xmin = jx + bb * ka;
		double kb = floor((jy - 1.0) / aa);
		int ymin = jy - aa * kb;
		int xmax = (cc - bb * ymin) / aa;
		int ymax = (cc - aa * xmin) / bb;
		if(xmax <= 0){//判定无正整数解 
			cout << xmin << ' ' << ymin << endl;
			continue;
		}
		else{
			cout << (ymax - 1) / aa + 1 << ' ' << xmin << ' ' << ymin << ' ' << xmax << ' ' << ymax << endl;		
		}	
	} 
	return 0;
}
本人第一次写题解，管理大大求过 QwQ。
具体哪里有错说一下吧QwQ

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...