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

题目描述

给定不定方程

• 若该方程无整数解，输出 $-1$。

• 若该方程有整数解，且有正整数解，则输出其正整数解的数量、所有正整数解中 $x$ 的最小值、所有正整数解中 $y$ 的最小值、所有正整数解中 $x$ 的最大值、以及所有正整数解中 $y$ 的最大值。

• 若方程有整数解，但没有正整数解，你需要输出所有整数解中 $x$ 的最小正整数值， $y$ 的最小正整数值。

注：

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

2. 整数解即为 $x,y$ 均为整数的解。

3. $x$ 的最小正整数值即所有 $x$ 为正整数的整数解中 $x$ 的最小值，$y$ 同理。

输入格式

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

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

输出格式

应输出 $T$ 行。

若该行对应的询问无整数解，一个数字 $-1$。

若该行对应的询问有整数解但无正整数解，包含 $2$ 个由空格隔开的数字，依次代表整数解中，$x$ 的最小正整数值，$y$ 的最小正整数值。

否则包含 $5$ 个由空格隔开的数字，依次代表正整数解的数量，正整数解中，$x$ 的最小值，$y$ 的最小值，$x$ 的最大值，$y$ 的最大值。

读入输出量较大，注意使用较快的读入输出方式

输入样例 #1

7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432

输出样例 #1

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

说明/提示

输入样例 #2

21
334088 509270 256407038078
211572 928813 16159999404
635980 275001 321882623272
983328 127329 88806673660
170998 79223 790473526147
457367 759428 617937003984
607541 512783 891926788836
531118 606423 365426492966
177929 4852 342756159282
255669 797685 132908264210
206112 107298 498823309709
115002 204040 253038611541
460377 14701 347879957354
652200 65890 908204755793
622510 179296 258173530644
316170 775524 121159649957
375090 415602 172278197804
163031 385435 736974194440
965939 258497 861012882991
214792 928904 829881634709
851620 365890 988149276178

输出样例 #2

3 28796 150501 538066 484589
524061 109596
2 11617 507632 286618 1143612
-1
58 71294 77059 4587005 9823945
2 332516 156062 1091944 613429
3 431494 13072 1457060 1228154
1 604922 72790 604922 72790
397 194 175244 1921586 70635128
-1
-1
-1
51 7238 418178 742288 23437028
-1
4 74982 245829 343926 1179594
-1
-1
11 374395 123387 4228745 1753697
4 45752 262062 821243 3159879
-1
-1

输入样例 #3

22
922031 449772 5048732481
827283 465919 322182454796
679020 808532 435177492127
461288 960329 44432193257
597488 176370 827145406407
436022 287911 968463903805
984597 951049 349944473798
53842 199086 16287021893
743010 156024 331791336
471027 742360 844587300304
226408 796607 488370797866
902054 562593 638802295359
270158 595483 879563611321
548105 785934 700739494924
531538 333289 936617104366
774937 40559 804812361003
537451 520465 977682398400
256141 990043 933718311996
495776 989347 586400816249
928915 798248 666683396020
935610 734314 548630563581
75101 605406 166606104584

输出样例 #3

240939 439332
454690 711437
-1
96703 461105
-1
8 111609 142583 2126986 3194737
699943 627920
-1
1608 118304
2 660232 247762 1402592 718789
19 34543 21054 2082961 603246
1 458235 400733 458235 400733
-1
1 785726 343641 785726 343641
5 219434 334114 1552590 2460266
25 37496 528101 1010912 19126589
3 442290 346852 1483220 1421754
4 346258 85103 3316387 853526
1 419976 382259 419976 382259
1 594636 143210 594636 143210
-1
3 427852 71920 1638664 222122

【数据范围】

对于 $100\%$ 的数据，$1 \le T \le 2 \times {10}^5$，$1 \le a, b, c \le {10}^9$。