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

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

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

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

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

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

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

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

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