min{Ax+By : Cx=Dy mod M, x,y > 0}

[MetaMorphy]

Всем привет. Да, такая вот простая с виду задача - найти

$\min\{Ax + By : Cx \equiv Dy \bmod M, x,y > 0\}$

при заданных целых положительных $A, B, C, D, M$ (значения $x, y$ тоже предполагаются целыми).

То, что её можно пытаться решать как задачу целочисленного линейного программирования (пусть и очень простую), понятно. Мне это показалось было стрельбой из пушки по воробьям, но попытавшись пойти напролом (см. ниже), я уже начал сомневаться...

Мой путь решения оказался таким. Во-первых, $A$ и $B$ можно считать взаимно простыми и найти $X,Y$ такие, что $AX - BY = 1, 0 < X < B, 0 < Y < A$. Пусть теперь $u = Ax + By, v = Yx + Xy$, тогда мы ищем

$\min\left\{u : (CX + DY)u \equiv (AD + BC)v \bmod M, \displaystyle\frac{Y}{A} < \displaystyle\frac{v}{u} < \displaystyle\frac{X}{B}\right\}$

(значения $u, v$ считаются целыми положительными). Далее, целые решения $u, v$ сравнения $Uu \equiv Vv \bmod M$ имеют вид

$u = \displaystyle\frac{(V,M)\alpha}{(U,V,M)}, v = \displaystyle\frac{UW\alpha}{(U,V)} + \displaystyle\frac{M\beta}{(V,M)}, W = \left(\displaystyle\frac{V(U,V,M)}{(U,V)(V,M)}\right)^{-1} \bmod \displaystyle\frac{M(U,V,M)}{(U,M)(V,M)},$

где $\alpha, \beta$ - произвольные целые, а выражения вида $(U,V,W)$ обозначают наибольший общий делитель (вроде, не напортачил).

В итоге получается задача минимизации $\alpha$ при ограничении вида $\displaystyle\frac{\beta_1}{\alpha_1} < \displaystyle\frac{\beta}{\alpha} < \displaystyle\frac{\beta_2}{\alpha_2}$. То есть (ещё одна, учитывая предыдущее) вариация алгоритма Евклида.

Вопрос напрашивается. Так и ломиться? Или назад в ЦЛП? Или, может, упростить можно...

P.S. Всякие граничные случаи я рассматривать не стал, и так текста многовато.