数论

· · 个人记录

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

给定不定方程

ax+by=c

若该方程无整数解，输出 -1。
若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中 x 的最小值，所有正整数解中 y 的最小值，所有正整数解中 x 的最大值，以及所有正整数解中 y 的最大值。
若方程有整数解，但没有正整数解，你需要输出所有整数解中 x 的最小正整数值， y 的最小正整数值。

正整数解即为 x, y 均为正整数的解，\boldsymbol{0} 不是正整数。
整数解即为 x,y 均为整数的解。

**【数据范围】** 对于 $100\%$ 的数据，$1 \le T \le 2 \times {10}^5$，$1 \le a, b, c \le {10}^9$。 先求出这个方程的解，用扩展欧几里得。 $$ax_0+by_0=\gcd(a, b)$$ 通过等式变换得到另一组特解。 $$x_1=x_0\times\frac{c}{\gcd(a,b)}$$ $$y_1=y_0\times\frac{c}{\gcd(a,b)}$$ 考虑寻找一组通解，设 $r\in \mathbb{Q}$。则有： $$a(x_1+rb)+b(y_1-ra)=c$$ 通解需保证为整数，即 $\{ra,rb\}\in\mathbb{Z}$。\ 当 $r=\frac{1}{\gcd(a, b)}$ 时，$ra$ 与 $rb$ 的值最小，即所有通解之差都不会小于它们，记 $r_x=\frac{a}{\gcd(a, b)},r_y=\frac{a}{\gcd(a, b)}