Другие языки программирования и технологии

Уравнение a*x+b*y=c

Задано уравнение: a*x+b*y=c, где a,b,c,x,y - целые неотрицательные числа. Заданы коэффициенты a,b,c. Требуется определить x,y. Формат ввода: a b c Формат вывода: каждая строка содержит пару x y, удовлетворяющую уравнению. Требуется найти все возможные решения. Решения должны быть отсортированы по возрастанию x. Ограничения: a<=10000, b<=10000, c<=10000
Лёха _-_-_-_-_
Лёха _-_-_-_-_
664
Обычное решение Диофантова уравнения в условиях ограниченного диапазона:
program diofant;
var
x, y: Integer;
a,b,c: integer;
begin
WriteLn('Целые решения уравнения aх + by = c из диапазона');
WriteLn('l <= x <= 10000, 1 <= у <= 10000,1 <= с <= 10000: ');
readln(a,b,c);
for x := 1 to 10000 do
for у := 1 to 10000 do
if (a*x + b*y = c )then
WriteLn('(x, y) = (', x, ', ', y, ')');
Write('Нажмите <enter>');
ReadLn;
end.
Сергей Колос
Сергей Колос
35 996
Лучший ответ
> найти все возможные решения

Бредятина.
Hamid Brisha
Hamid Brisha
32 502
Иван Королев Никакой бредятины нет, это задача на циклы
Ваня ??????? Точно, бредятина. Видно же, что имеем обычное линейное уравнение. То есть для любого х всегда найдется соответствующий y. Ты что, этого не видишь???
Ну так y=(c-a*x)/b
А дальше гоняй цикл для x и ищи y

Да, максимум для x — это c/a, а то ещё погонишь цикл к бесконечности
Влад Белоус
Влад Белоус
7 348
Лёха _-_-_-_-_ Можно попдробнее, какой цикл? Как раз это и не понимаю
Ваня ??????? Еще один дятел. Прочитай - ему нужны ВСЕ решения. А их - как чисел на числовой прямой.
Ваня ??????? И при чем тут цикл?
Ваня ??????? И что же мне откроется? Что уравнение y = x при абсолютно целых коэффициентах имеет областью изменения и областью определения ВСЮ числовую ось? Или против этого ты тоже будешь возражать?
Алгоритм решения этой задачи называется Расширенный алгоритм Евклида. Почитай в ВИкипедии на эту тему.
Денис Домнышев
Денис Домнышев
2 075
Лёха _-_-_-_-_ та немного не то что надо.
#include

int gcd(int a, int b, int&x, int&y) {
if (a == 0) {
x = 0, y = 1;
return b;
}
int x1, y1;
int d = gcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a, b, c;
cin >> a >> b >> c;
int x, y;
int d = gcd(a, b, x, y);
if (c % d != 0) {
cout << "Impossible\n";
return 0;
}
x = x * c / d;
y = y * c / d;
// теперь можешь выводить: ab + xy = c, в переменных ответы
}
АШ
Анатолий Шешнев
343
Анатолий Шешнев Забыл, что тебе еще все решения нужны.
Для этого нужно делать такую штуку.

int cur_x = x + k * b / d;
int cur_y = y - k * a / d;

где k принадлежит целым числам. Получается крутишь цикл от 0 до какого-то значения, и выводишь ответы
(x+c)×b=c
Антон Ермоленко
Антон Ермоленко
106

Похожие вопросы