e-olymp
Змагання

Euclidean Extended algorithm

Задача Евкліда

Ще з часів Евкліда відомо, що для довільних натуральних чисел a та b завжди існують такі цілі x та y, що ax + by = d, де d - найбільший спільний дільник a та b. В цій задачі за заданими a та b слід знайти відповідні x, y та d.

Вхідні дані

Кожний рядок містить два натуральні числа a та b (a, b109).

Вихідні дані

Для кожногї пари a та b в окремому рядку вивести три цілі числа x, y та d, розділені пропуском. Якщо шуканих значень x та y декілька, то слід вивести таку пару, для якої значення |x| + |y| найменше. Якщо і таких пар декілька, то вивести ту пару, в якій x мінімальне.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 6
17 17
5 3
Вихідні дані #1
-1 1 2
0 1 17
-1 2 1