A4935 | $【模板】二元一次不定方程 (exgcd)$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定不定方程 $$ax+by=c$$ 若该方程无整数解，输出 $-1$。 若该方程有整数解，且有正整数解，则输出其**正整数**解的数量，所有**正整数**解中 $x$ 的最小值，所有**正整数**解中 $y$ 的最小值，所有**正整数**解中 $x$ 的最大值，以及所有**正整数**解中 $y$ 的最大值。 若方程有整数解，但没有正整数解，你需要输出所有**整数解**中 $x$ 的最小正整数值， $y$ 的最小正整数值。 正整数解即为 $x, y$ 均为正整数的解，$\boldsymbol{0}$ **不是正整数**。 整数解即为 $x,y$ 均为整数的解。 $x$ 的最小正整数值即所有 $x$ 为正整数的整数解中 $x$ 的最小值，$y$ 同理。

第一行一个正整数 $T$，代表数据组数。 接下来 $T$ 行，每行三个由空格隔开的正整数 $a, b, c$。

$T$ 行。 若该行对应的询问无整数解，一个数字 $-1$。 若该行对应的询问有整数解但无正整数解，包含 $2$ 个由空格隔开的数字，依次代表整数解中，$x$ 的最小正整数值，$y$ 的最小正整数值。 否则包含 $5$ 个由空格隔开的数字，依次代表正整数解的数量，正整数解中，$x$ 的最小值，$y$ 的最小值，$x$ 的最大值，$y$ 的最大值。 **读入输出量较大，注意使用较快的读入输出方式**

输入 #1

输出 #1

4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56

C++ 编辑器

输入

输出