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

Задачи из рубрикатора

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

Условие задачи  
ID 31903
Расширенный алгоритм Евклида
Темы: Расширенный алгоритм Евклида   

Даны натуральные числа \(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

ID 33656
Диофантовы уравнения
Темы: Расширенный алгоритм Евклида   

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

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

Выходные данные
Выведите ответ на задачу.

Примечание
Сложность алгоритма должна быть равна сложности алгоритма Евклида + константа.
 
Примеры
Входные данные Выходные данные
1 1 2 3 1 1
2 10 6 8 2 -2