题解 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。