Problem A
Extended GCD

Útfærðu reiknirit til að finna stærsta sameiginlega þátt tveggja heiltalna $a$ og $b$, oft táknað með $\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=\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}\le u,v\le {10}^{18}$.

Stigagjöf

6
15

3
-2
1

4
0

4
1
0

6
15

3
3
-1