Уравнение axy+bx+cy = d

← →
partizan (2007-05-23 21:19) [0]

Как определить, имеет-ли уравнение
axy+bx+cy = d
решение в целых неотрицательных числах?
(Все коеффициенеты тоже целые, не отрицательные)

Интересует именно ответ на вопрос "Есть такие решения или нет?", хотя если кто предложит и сам алгоритм нахождения этих решений - тоже хорошо.

Есть идеи по этому поводу?

← →
wp2 © (2007-05-23 21:31) [1]

не понял, а сколько там не известных???

Если две х и Y, то надо же и два уравнения!

← →
Юрий Зотов © (2007-05-23 21:39) [2]

> partizan (23.05.07 21:19)

Имеет наверняка. Например, при a=b=c=1, d=3.

← →
wp2 © (2007-05-23 21:44) [3]

А алгоритм для решений уравнений есть всегда, например, методом деления пополам.

← →
Alx2 © (2007-05-23 21:52) [4]

>wp2 © (23.05.07 21:44)

Причем, наверняка, классная и твердая такая уверенность... :)

← →
TUser © (2007-05-23 21:52) [5]

> в целых неотрицательных числах?

При d=0 :)

← →
Alx2 © (2007-05-23 21:58) [6]

>partizan (23.05.07 21:19)

Навскидку: при хотябы одном ненулевых целых a,b,c есть, кажется, бесконечное множество решений. Надо покумекать.

← →
Alx2 © (2007-05-23 22:11) [7]

Нет, [6] - не то

← →
ferr © (2007-05-23 22:23) [8]

y = (d - b * x) / (a * x + c);
рассматривая такие x что {d - b * x >= 0} проверяем делится ли эта дробь нацело. Вычислительная сложность (O(d / b)), явно можно гораздо быстрее =)

← →
partizan (2007-05-23 23:13) [9]

1) Не достаточно точно сформулировал условие:

Для заданных a, b, c, d нужно сказать, существуют-ли такие х и у.

2) Речь идет об очень больших числах, таких, которые используются в криптографии. Так что сложность O(d / b) не подходит, должно быть максимум log(D) (Полиномиально, относительно количества разрядов)

← →
partizan (2007-05-23 23:15) [10]

> Нет, [6] - не то

Не то, уже нашел доказательство того, что их конечное множество

← →
partizan (2007-05-23 23:25) [11]

[10] - кроме некоторых частных случаев

>partizan (23.05.07 23:25)

Чудится мне, это все к подобному пифагорейским тройкам можно пробразовать.

Уравнение axy+bx+cy = d Найти похожие ветки