1

Тема: Ошибки в статье "Линейные диофантовы уравнения с двумя переменными"

Раздел "Получение всех решений".

x = y0 + k * b / g;

Правильно будет

x = x0 + k * b / g;


В разделе "Нахождение количества решений и сами решения в заданном отрезке" код

int    a, b, c, g, // коэффициенты диофантова уравнения, и g=gcd(a,b)
    x0, y0, // одно из решений диофантова уравнения
    x1, x2, // заданный отрезок
    mx, my; // искомое решение с наименьшим x >= x1
int cnt = (x1 - x0) / b;
if (x0 + cnt * b < x1)
    ++cnt;
mx = x0 + cnt * b;
my = y0 - cnt * b;

следует заменить на:

int    a, b, c, g, // коэффициенты диофантова уравнения, и g=gcd(a,b)
    x0, y0, // одно из решений диофантова уравнения
    x1, x2, // заданный отрезок
    mx, my; // искомое решение с наименьшим x >= x1
int cnt = (x1 - x0) * g / b;
if (x0 + cnt * b / g < x1)
    ++cnt;
mx = x0 + cnt * b / g;
my = y0 - cnt * a / g;

2

Re: Ошибки в статье "Линейные диофантовы уравнения с двумя переменными"

Ой, как много ошибок... Спасибо.

3

Re: Ошибки в статье "Линейные диофантовы уравнения с двумя переменными"

Я конечно мало что в этом понимаю, но мне кажется, что формула (ymax-ymin)/abs(b/g) неверна. Если изначально выбрать такие ограничения, что x1=x2 и y1=y2, то получается, что решений либо же вообще не существует, либо существует одно решение (собственно x1, y1), в последнем случае получается, что ymax=ymin=y1=y2 и формула выдаст 0 (так как в числителе (ymax-ymin) получается 0), хотя правильный ответ 1. Возможно правильная формула (ymax-ymin)/abs(b/g)+1?

4

Re: Ошибки в статье "Линейные диофантовы уравнения с двумя переменными"

Astekinane
Да, так и есть - мы же не длину отрезка считаем, а число целых точек на отрезке.


Кстати, очень хотелось бы, чтобы кто-нибудь пострессил те решения, которые описаны в статье. У меня нет уверенности, что они абсолютно корректны на всяких вырожденных/отрицательных входных данных.