Hide
Problem A
Extended GCD
Languages
en
is
Implement an algorithm to find the greatest common divisor of two integers $a$ and $b$, often denoted by $\mathrm{gcd}(a, b)$.
Input
Input is two lines. The fyrst line contains the integer $a$. The second line contains the integer $b$.
Output
Output three lines. The first line should contain the integer $g$, where $g = \mathrm{gcd}(a, b)$ and $g = ua + vb$. The second line should contain the integer $u$. The third line should contain the integer $v$.
Scoring
|
Group |
Points |
Constraints |
|
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$ and $u$ should be minimized. |
| 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 |
