Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Расширенный алгоритм Евклида

Расширенный алгоритм Евклида

Даны натуральные числа \(a, b, c.\) Если уравнение \(a \cdot x + b \cdot y = c\) имеет решения в целых числах, то выведите через пробел \(НОД(a,b)\), \(x\) и \(y\) (какое-нибудь решение). Если решения не существует, то выведите слово Impossible.
 
Входные данные: Входные данные - натуральные числа и не превышают по модулю 10000.
Выходные данные: Выведите ответ на задачу.

Примеры
Входные данные Выходные данные
1 1 2 3 1 1 1
2 10 6 8 2 2 -2

Диофантовы уравнения

Расширенный алгоритм Евклида

Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите слово Impossible.

Входные данные: Вводятся три натуральных числа.
Выходные данные: Выведите ответ на задачу.

Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.

Примеры
Входные данные Выходные данные
1 1 2 3 1 1
2 10 6 8 2 -2