Редкое имя(#1008) Вирусы(#1010)
#1009

Задача g6_1009: Уравнение. (castle.ssu.samara.ru/olymp/ - задача 1010)
входной файл: input.txt
файл результата: output.txt
время на тест: 1 секунда
Задано уравнение:
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
Пример входного файла:
1 1 3
Файл результата для данного примера:
0 3
1 2
2 1
3 0
Решение g6_1009:
Это простая задача. Только сначала надо все хорошенько представить на бумаге.
Из уравнения ax + by = c выразим x:
x = (c - by) / a;
Т.к. коэффициенты целые и неотрицательные, то
Xmax = c / a; - при y = 0;
Затем выражаем y через x:
y = (c - ax) / b;
Перебираем все целые x от 0 до Xmax, получаем для них значения y, если y целое - выводим.
Просто!

Наверх