Скачать: CL | DM;

Уравнение 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] - кроме некоторых частных случаев

---

← →
Alx2 ©   (2007-05-23 23:35) [12]

>partizan   (23.05.07 23:25)

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.47 MB
Время: 0.017 c