Hide
Problem A
Extended GCD
Languages
en
is
Útfærðu reiknirit til að finna stærsta sameiginlega þátt tveggja heiltalna $a$ og $b$, oft táknað með $\mathrm{gcd}(a, b)$.
Inntak
Inntak er tvær línur. Fyrsta línan inniheldur heiltöluna $a$. Önnur línan inniheldur heiltöluna $b$.
Úttak
Skrifaðu út þrjár línur. Fyrsta línan skal innihalda heiltöluna $g = \mathrm{gcd}(a, b)$ og $g = ua + vb$. Önnur línan skal innihalda heiltöluna $u$. Þriðja línan skal innihalda heiltöluna $v$. Tölurnar $u$ og $v$ verða að uppfylla $-10^{18} \leq u, v \leq 10^{18}$.
Stigagjöf
|
Hópur |
Stig |
Takmarkanir |
|
1 |
60 |
$1 \leq a, b \leq 10^{18}$. |
|
2 |
20 |
$0 \leq a, b \leq 10^{18}$. |
|
3 |
20 |
$0 \leq a, b \leq 10^{18}$, $u > 0$ og $u$ skal vera lágmarkað. |
| Sample Input 1 | Sample Output 1 |
|---|---|
6 15 |
3 -2 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 0 |
4 1 0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 15 |
3 3 -1 |
