Три задачи с одним решением

Интересная статья от IronPeter. Осторожно. Мат и Матан.

Есть три задачи. Задача первая — решить матричное уравнение A x = b, где A — матрица, x — неизвестный вектор, а b — заданная правая часть, опять вектор. Коэффициенты — действительные числа. Во второй задаче коэффициенты (и у матрицы и у векторов) — целые числа. А в третьей задаче все то же самое, только коэффициенты целые положительные, и уравнение надо решить в целых положительных числах. Накал пиздеца постепенно крепчает. Целые числа мы не всегда можем делить друг на друга. Впрочем, взяв пару чисел (a, b), мы можем вычесть из большего по модулю числа меньшее по модулю, и такая процедура редукции нам отлично заменит деление. А целые положительные числа мы можем вычитать, только меньшее из большего.

Читать дальше