b050: exgcd
標籤 :
通過比率 : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-11-19 21:20

內容

给定不定方程式$ax+by=c$若该方程无整数解,输出 −1
若该方程有整数解,且有正整数解,则输出其正整数解的数量,所有正整数解中$x$的最小值,所有正整数解中$y$的最小值,所有正整数解中$x$的最大值,以及所有正整数解中$y$的最大值。
若方程有整数解,但没有正整数解,你需要输出所有整数解中$x$的最小正整数值,$y$的最小正整数值。

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

輸入說明

第一行有一數$T$ ($T\leq 2\times 10^5$)

接下來有$T$行,每行有三個正整數字$a,b,c$,$0 < a,b,c\leq 10^9$

輸出說明

請依上述題目輸出

範例輸入
7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432
範例輸出
4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 10.0s , <10M
公開 測資點#1 (50%): 1.0s , <10M
提示 :
標籤:
出處:
luogu P5656 [管理者:
william1010121 (郭勝威)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」