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

· · 题解

本题的出题人来放一个题解~

以这道题为模板，洛谷上所有\text{exgcd}的题直接改改都能过（

ax+by=c

显然有 \gcd(a,b)|(ax+by) ，故若 c 不是 \gcd(a,b) 的倍数直接无解

我们已知\text{exgcd}可以求出

ax+by=\gcd(a,b)

的一组整数特解，我们记为 x_0 与 y_0

则有

ax_0+by_0=\gcd(a,b) a\frac{x_0c}{\gcd(a,b)}+b\frac{y_0c}{\gcd(a,b)}=c

故我们已经找到了原方程的一组整数特解，记为 x_1 和 y_1

x_1=\frac{x_0c}{\gcd(a,b)}, y_1=\frac{y_0c}{\gcd(a,b)}

那么我们考虑构造原方程整数通解形式

我们设任意 d \in \mathbb{Q} ，那么必有

a(x_1+db)+b(y_1-da)=c

（自行拆括号，直接消掉）

同时，通解需要保证 x_1+db 与 y_1-da 均为整数

因为 x_1 , y_1 为整数，我们只需要保证

db \in \mathbb{Z} $，$da \in \mathbb{Z}

令当 d 取到最小的可能的正值时的 d_x=db，d_y=da ，那么任意解中这两个变量与 x_1 y_1 的偏差一定分别是 d_x 与 d_y 的倍数

显然最小时 d_x=\frac{b}{\gcd(a,b)} ， d_y=\frac{a}{\gcd(a,b)}，在d=\frac{1}{\gcd(a,b)} 时取到

那么通解形式就出来了，

x=x_1+sd_x y=y_1-sd_y

其中，s 是任意整数

而且，随着 x 增大 y 减小 （废话，它们的和一定）

而且，s 越大，x 越大，y 越小，反之亦然（重点）

故我们可以继续解题：

若我们限制 x>0，有x_1+sd_x>0，s>-\frac{x_1}{d_x}

若我们限制 y>0，有y_1-sd_y>0，s<\frac{y_1}{d_y}

那么我们有 -\frac{x_1}{d_x}<s<\frac{y_1}{d_y}

因为 s 是整数，故有

\lceil\frac{-x_1+1}{d_x}\rceil\leq s\leq\lfloor\frac{y_1-1}{d_y}\rfloor

若 \lceil\frac{-x_1+1}{d_x}\rceil> \lfloor\frac{y_1-1}{d_y}\rfloor，那么显然不可能让两个都是正整数（因为没有合法的 s）

此时，答案即为没有正整数解但有整数解，x 最小即为s=\lceil\frac{-x_1+1}{d_x}\rceil时 x 的值，y 最小即为s=\lfloor\frac{y_1-1}{d_y}\rfloor时 y 的值

否则，就有正整数解，正整数解个数即为 s 的合法整数取值个数，算好上下界直接做。

而最大最小值什么的，x 的最大值和 y 的最小值都是在 s 最大时取到，而 x 的最小值和 y 的最大值都是在 s 最小时取到，直接计算即可。

其实这些玩意是可以化简为更简单的形式的（详见其他题解），但我认为这个解题思路最容易让初学者理解。

代码就不放了，丑死了，照着题解里公式敲一遍就完事了。

关于坑点：

开long long。