二元一次不定方程 (exgcd)

方程 (exgcd)"/>

二元一次不定方程 (exgcd)

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

题目链接

题目描述

给定不定方程

​ ax + by = c

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

正整数解即为 x,y 均为正整数的解，0 不是正整数。
整数解即为 x,y 均为整数的解。
x 的最小正整数值即所有 x 为正整数的整数解中 x的最小值，y 同理。

输入格式

第一行一个正整数 T，代表数据组数。

接下来 T 行，每行三个由空格隔开的正整数 a, b, c。

输出格式

T 行。

若该行对应的询问无整数解，一个数字 -1。
若该行对应的询问有整数解但无正整数解，包含 22 个由空格隔开的数字，依次代表整数解中，x的最小正整数值，y的最小正整数值。
否则包含 5 个由空格隔开的数字，依次代表正整数解的数量，正整数解中，x 的最小值，y 的最小值，x 的最大值，y的最大值。

题解

由线性同余方程相关定理以及裴蜀定理（贝祖定理）可知，当且仅当gcd(a,b)|c时，方程有整数解。令d = gcd(a,b), x 0 = d x c , y 0 = d y c x_0=\frac{dx}{c},y_0=\frac{dy}{c} x0​=cdx​,y0​=cdy​
a x 0 + b y 0 = d    ① ax_0 + by_0 = d\ \ ① ax0​+b