| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм Евклида для решения ax+by=1 |
| Автор: whoever 5.4.2008, 22:39 |
| http://algolist.manual.ru/maths/teornum/nod.php#3 Можно ли его модифицировать так, чтобы все операции проводились только с неотрицательными числами? Важно только получение коэффициента при меньшем из a и b. |
| Автор: maxim1000 6.4.2008, 00:21 |
| имеется в виду ax+by=1 или ax+by=1 mod m? (потому что ответы для этих случаев будут разные) |
| Автор: whoever 6.4.2008, 09:47 |
| ax + by = 1. Изначально уравнение имеет вид by = 1 (mod a). |
| Автор: maxim1000 6.4.2008, 11:18 |
| ну тогда без отрицательных чисел не получится отбросим случай, когда одно из чисел =1 тогда какие бы ни были a и b>0, a*x+b*y будет >=x+y>1 т.е. отрицательные числа не просто возможны - один из коэффициентов всегда будет отрицательным |
| Автор: whoever 6.4.2008, 11:25 |
| Именно отрицательный коэффициент мне и не нужен. Поэтому, может быть, его положительной заменой можно добиться неизменности другого коэффициента? |
| Автор: maxdiver 6.4.2008, 17:01 | ||
whoever
Значит, требуется найти его решение при y>0. Значит, нужно решить уравнение ax + by = 1 при y>0, а x может быть любым. Тогда решение такое: находим любое решение этого уравнения алгоритмом Евклида, а затем приводим y к положительному, пользуясь такой операцией (корректность которой очевидна): к y прибавить a, а от x отнять b. |
| Автор: maxim1000 6.4.2008, 19:17 | ||
нет, не получится я ж написал, что при обоих положительных коэффициентах результат никак не может равняться 1 ну разве что числа, перед которыми коэффициенты ищутся, могут быть отрицательными? |
| Автор: whoever 6.4.2008, 19:24 |
| а > b >= 0, x < 0, y > 0. Кажется, Вы меня неверно поняли. В процессе вычисления x и y не имеется возможности использовать отрицательные числа. Каким будет в итоге x - неважно. Так вот: можно ли чем-то положительным в процессе вычисления заменять x, чтобы y остался правильным (т.е., не вычитать q*E[0][0] и q*E[1][0] из правого столбца, а прибавлять что-то другое). Естественно, одно из x и y должно быть меньше нуля, но так как x < 0 неважен, с ним можно делать что угодно. |
| Автор: v2v 6.4.2008, 19:46 |
| пройди этот алгоритм до конца - найди д. потом методом подбора, увеличивая на 1 y найди подходящих х . |
| Автор: maxim1000 6.4.2008, 21:41 | ||
хм... тогда не очень понятна природа ограничения... можно поподробнее описать его причины? а то, обычно, если нельзя использовать отрицательные числа, значит, нет возможности их и получить... ну разве что это ограничение для всех операций кроме последней? |
