Задача 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 целое - выводим.
Просто!