e-olymp
Yarışlar

Azerbaijan Programming Olympiad - 2nd Stage preparation

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

Со времен Евклида известно, что для любых натуральных чисел 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 минимально.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 6
17 17
5 3
Çıxış verilənləri #1
-1 1 2
0 1 17
-1 2 1