Форумы-->Форум для внеигровых тем-->
1|2|3
| Автор | Помогите с математикой! |
|---|
может и ткие ришения быть
1.решение
Расширенный алгоритм Евклида по заданным A и B находит их наибольший общий делитель G, а также такие коэффициенты Xg, Yg, что:
A Xg + B Yg = G
Если C делится на G = gcd(A,B), то диофантово уравнение A X + B Y = C имеет решение; в противном случае диофантово уравнение решений не имеет.
Предположим, что C делится на G, тогда, очевидно, выполняется:
A Xg (C/G) + B Yg (C/G) = C
т.е. одним из решений диофантова уравнения являются числа:
X0 = Xg C / G
Y0 = Yg C / G
2.решение
Покажем, как получить все остальные решения (а их бесконечное множество) диофантова уравнения, зная одно из решений (X0, Y0).
Итак, пусть G = gcd(A,B), а числа X0, Y0 удовлетворяют условию:
A X0 + B Y0 = C
Тогда заметим, что, прибавив к X0 число B/G и одновременно отняв A/G от Y0, мы не нарушим равенства:
A (X0 + B/G) + B (Y0 - A/G) =
= A X0 + A B / G + B Y0 - B A / G =
= A X0 + B Y0 =
= C
Очевидно, что этот процесс можно повторять сколько угодно, т.е. все числа вида:
X = X0 + K B/G,
Y = Y0 - K A/G,
K ∈ Z
являются решениями диофантова уравнения.
Более того, только числа такого вида и являются решениями, т.е. мы описали множество всех решений диофантова уравнения (оно получилось бесконечным, если не наложено дополнительных условий).
3.решение
Пусть даны два отрезка [X1;X2] и [Y1;Y2], и требуется найти количество решений (X,Y) диофантова уравнения, лежащих в данных отрезках соответственно.
Сначала найдём решение с наименьшим X = MinX таким, что MinX ∈ [X1;X2]. Для этого сначала найдём любое решение диофантова уравнения (см. пункт 1). Затем получим из него решение с наименьшим MinX ∈ [X1;X2] - воспользуемся процедурой, описанной в пункте 2, и будем уменьшать/увеличивать MinX, пока оно не попадёт в заданный отрезок, и при этом будет наименьшим. Это можно сделать за O (1) таким образом:
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;
Здесь предполагается, что B > 0 (если B < 0, то нужно предварительно изменить знаки A, B и C).
Аналогичным образом найдём решение с наибольшим X = MaxX ∈ [X1;X2].
Теперь, если MinX > MaxX, то количество решений равно нулю.
Если же MinX <= MaxX, то нам осталось наложить условие на Y: Y ∈ [Y1;Y2].
Пусть MinY и MaxY - это соответствующие пары для MinX и MaxX. Если MinY > MaxY, то обменяем их значения. Нам нужно найти пересечение отрезка [MinY;MaxY] и [Y1;Y2]. Будем увеличивать MinY (на |A/G|), пока оно не станет больше либо равно Y1, и будем уменьшать MaxY (опять же, на |A/G|), пока оно не станет меньше либо равно Y2 (выполняя это, мы не нарушим ограничения на X, поскольку уменьшая MinY, мы только увеличиваем соответствующий ему MinX, аналогично и для MaxY).
В конце концов ответом на задачу будет являться величина (MaxY - MinY) / |A/G|.
Таким образом, мы можем найти количество решений в заданном отрезке за O (log max(A,B)).
Аналогичным образом можно получить и сами решения, лежащие в заданном отрезке.
4.решение
Здесь на X и на Y также должны быть наложены какие-либо ограничения, иначе ответом практически всегда будет минус бесконечность.
Но идея решения такая же, как в предыдущем пункте: сначала находим любое решение диофантова уравнения, затем, применяя описанную в пункте 2 процедуру, придём к наилучшему решению.
Действительно, мы имеем право выполнить следующее преобразование (см. пункт 2):
X += K B/G,
Y -= K A/G,
K ∈ Z
Заметим, что при этом сумма X+Y меняется следующим образом:
(X + K B/G) + (Y - K A/G) =
= X + Y + K (B/G - A/G)
Т.е. если A < B, то нужно выбрать как можно меньшее значение K, если A > B, то нужно выбрать как можно большее значение K.
Если A = B, то мы никак не сможем у | | Как ты собрался это к прямым прикручивать, если у тебя речь про отрезки? | Как насчёт этого.
Будем искать точку пересечения, как линейную комбинацию векторов p=(B,-A) и q=(b,-a) (эти вектора показывают направления прямых). Пусть точка представима в виде alfa*p+beta*q.
Из первого уравнения получаем, что (alfa*p+beta*q)*(A,B)=-C. Так как p*(B,-A)=0, получаем, что beta=-C/(b*A-a*B).
Аналогично находим alfa.
Зная alfa, beta, p, q, находим ответ. | для Sat-9:
по заданным A и B находит их наибольший общий делитель G.
Дальше можно не читать. С какой стати A и B целые? | | всем спасибо, сделал с параметризацией, в конце концов, я же таким образом решал 1 линейное уравнение, а не систему. | | тема закрыта by Аэнаин (2009-09-16 18:55:57) |
|---|
1|2|3К списку тем
|
