Шугаман Диофантын тэгшитгэл¶

Шугаман Диофантын тэгшитгэл (хоёр хувьсагчтай) нь дараах ерөнхий хэлбэртэй тэгшитгэл юм:

$$ax + by = c$$

энд $a$, $b$, $c$ нь өгөгдсөн бүхэл тоо, $x$, $y$ нь үл мэдэгдэх бүхэл тоо.

Энэ өгүүлэлд бид эдгээр тэгшитгэлийн хэд хэдэн сонгодог бодлогыг авч үзнэ:

нэг шийд олох
бүх шийдийг олох
өгөгдсөн интервал дахь шийдийн тоо ба шийдүүдийг өөрсдийг нь олох
$x + y$-ийн хамгийн бага утгатай шийдийг олох

Degenerate case¶

Анхаарах ёстой degenerate case бол $a = b = 0$ үе юм. $c = 0$ эсэхээс хамааран бид шийдгүй эсвэл төгсгөлгүй олон шийдтэй болохыг харахад амархан. Энэ өгүүллийн үлдсэн хэсэгт бид энэ тохиолдлыг үл тоомсорлоно.

Аналитик шийд¶

$a \neq 0$ ба $b \neq 0$ үед $ax+by=c$ тэгшитгэлийг дараах хоёрын аль нэгтэй эквивалентаар авч үзэж болно:

$$\begin{align} ax &\equiv c \pmod b \\ by &\equiv c \pmod a \end{align}$$

Ерөнхий чанарыг алдагдуулалгүйгээр $b \neq 0$ гэж үзээд эхний тэгшитгэлийг авч үзье. $a$ ба $b$ харилцан анхны үед түүний шийд нь дараах байдлаар өгөгдөнө

$$x \equiv ca^{-1} \pmod b,$$

энд $a^{-1}$ нь $b$ модулиар авсан $a$-гийн модулийн урвуу юм.

$a$ ба $b$ харилцан анхны биш үед бүх бүхэл $x$-ийн хувьд $ax$-ийн $b$ модулиар авсан утгууд нь $g=\gcd(a, b)$-д хуваагдана, тиймээс шийд зөвхөн $c$ нь $g$-д хуваагдах үед оршино. Энэ тохиолдолд тэгшитгэлийг $g$-ээр хураах замаар нэг шийдийг олж болно:

$$(a/g) x \equiv (c/g) \pmod{b/g}.$$

$g$-ийн тодорхойлолтоор $a/g$ ба $b/g$ тоонууд харилцан анхны байх тул шийд нь тодорхой байдлаар дараах хэлбэртэй байна

$$\begin{cases} x \equiv (c/g)(a/g)^{-1}\pmod{b/g},\\ y = \frac{c-ax}{b}. \end{cases}$$

Алгоритмын шийд¶

Безугийн лемм (Безугийн адилтгал гэж бас нэрлэдэг) нь дараах шийдийг ойлгоход хэрэгтэй үр дүн юм.

$g = \gcd(a,b)$ гэе. Тэгвэл $ax + by = g$ байх $x,y$ бүхэл тоонууд оршино.

Түүнчлэн $g$ нь $ax + by$ хэлбэрээр бичигдэх хамгийн бага эерэг бүхэл тоо бөгөөд $ax + by$ хэлбэрийн бүх бүхэл тоо нь $g$-ийн үржвэр байна.

Хоёр үл мэдэгдэхтэй Диофантын тэгшитгэлийн нэг шийдийг олохын тулд Өргөтгөсөн Евклидийн алгоритм-ыг ашиглаж болно. Эхлээд $a$ ба $b$ сөрөг биш гэж үзье. $a$ ба $b$-д Өргөтгөсөн Евклидийн алгоритмыг хэрэглэхэд бид тэдгээрийн хамгийн их ерөнхий хуваагч $g$ ба дараах нөхцөлийг хангах $x_g$, $y_g$ хоёр тоог олж болно:

$$a x_g + b y_g = g$$

Хэрэв $c$ нь $g = \gcd(a, b)$-д хуваагддаг бол өгөгдсөн Диофантын тэгшитгэл шийдтэй, эсрэг тохиолдолд ямар ч шийдгүй. Баталгаа нь маш энгийн: хоёр тооны шугаман комбинац нь тэдгээрийн ерөнхий хуваагчид хуваагдана.

Одоо $c$ нь $g$-д хуваагдана гэж үзвэл бидэнд дараах илэрхийлэл гарна:

$$a \cdot x_g \cdot \frac{c}{g} + b \cdot y_g \cdot \frac{c}{g} = c$$

Тиймээс Диофантын тэгшитгэлийн нэг шийд нь:

$$x_0 = x_g \cdot \frac{c}{g},$$

$$y_0 = y_g \cdot \frac{c}{g}.$$

Дээрх санаа нь $a$ эсвэл $b$, эсвэл хоёул сөрөг байсан ч ажиллана. Бид зөвхөн шаардлагатай үед $x_0$ ба $y_0$-ийн тэмдгийг өөрчлөх хэрэгтэй.

Эцэст нь энэ санааг дараах байдлаар хэрэгжүүлж болно ($a = b = 0$ тохиолдлыг энэ код авч үзээгүйг анхаараарай):

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g) {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;
    return true;
}

Бүх шийдийг олох¶

Нэг шийд $(x_0, y_0)$-ээс өгөгдсөн тэгшитгэлийн бүх шийдийг гаргаж авч болно.

$g = \gcd(a, b)$ гэе, мөн $x_0, y_0$ нь дараах нөхцөлийг хангах бүхэл тоо байг:

$$a \cdot x_0 + b \cdot y_0 = c$$

Одоо $x_0$ дээр $b / g$ нэмж, зэрэгцээгээр $y_0$-ээс $a / g$ хасахад тэнцэл эвдрэхгүйг харах хэрэгтэй:

$$a \cdot \left(x_0 + \frac{b}{g}\right) + b \cdot \left(y_0 - \frac{a}{g}\right) = a \cdot x_0 + b \cdot y_0 + a \cdot \frac{b}{g} - b \cdot \frac{a}{g} = c$$

Мэдээжийн хэрэг энэ үйлдлийг дахин давтаж болох тул дараах хэлбэрийн бүх тоо:

$$x = x_0 + k \cdot \frac{b}{g}$$

$$y = y_0 - k \cdot \frac{a}{g}$$

нь өгөгдсөн Диофантын тэгшитгэлийн шийд болно.

Тэгшитгэл шугаман тул бүх шийд нэг шулуун дээр оршино, мөн $g$-ийн тодорхойлолтоор энэ бол өгөгдсөн Диофантын тэгшитгэлийн бүх боломжит шийдийн олонлог юм.

Өгөгдсөн интервал дахь шийдийн тоо ба шийдүүдийг олох¶

Өмнөх хэсгээс харахад хэрэв бид шийдэд ямар ч хязгаарлалт тавихгүй бол тэдгээр нь төгсгөлгүй олон байх нь тодорхой. Тиймээс энэ хэсэгт бид $x$ ба $y$-ийн интервалд зарим хязгаарлалт нэмж, бүх шийдийг тоолж, жагсаахыг оролдоно.

$[min_x; max_x]$ ба $[min_y; max_y]$ хоёр интервал байг, мөн бид зөвхөн эдгээр хоёр интервал дахь шийдийг олохыг хүсэж байна гэе.

Хэрэв $a$ эсвэл $b$ нь $0$ бол бодлого зөвхөн нэг шийдтэй болохыг анхаараарай. Энэ тохиолдлыг бид энд авч үзэхгүй.

Эхлээд бид $x \ge min_x$ байх, $x$-ийн хамгийн бага утгатай шийдийг олж болно. Үүний тулд эхлээд Диофантын тэгшитгэлийн дурын шийдийг олно. Дараа нь энэ шийдийг $x \ge min_x$ болтол шилжүүлнэ (өмнөх хэсэгт бүх шийдийн олонлогийн талаар мэдсэн зүйлээ ашиглан). Үүнийг $O(1)$-д хийж болно. $x$-ийн энэ хамгийн бага утгыг $l_{x1}$ гэж тэмдэглэе.

Үүнтэй адилаар $x \le max_x$ байх $x$-ийн хамгийн их утгыг олж болно. $x$-ийн энэ хамгийн их утгыг $r_{x1}$ гэж тэмдэглэе.

Үүнтэй адилаар $y$-ийн хамгийн бага утга $(y \ge min_y)$ ба хамгийн их утга $(y \le max_y)$-г олж болно. Харгалзах $x$-ийн утгуудыг $l_{x2}$ ба $r_{x2}$ гэж тэмдэглэе.

Эцсийн шийд бол $[l_{x1}, r_{x1}]$ ба $[l_{x2}, r_{x2}]$-ийн огтлолцолд орших $x$-тэй бүх шийд юм. Энэ огтлолцлыг $[l_x, r_x]$ гэж тэмдэглэе.

Following is the code implementing this idea. Notice that we divide $a$ and $b$ at the beginning by $g$. Since the equation $a x + b y = c$ is equivalent to the equation $\frac{a}{g} x + \frac{b}{g} y = \frac{c}{g}$, we can use this one instead and have $\gcd(\frac{a}{g}, \frac{b}{g}) = 1$, which simplifies the formulas.

void shift_solution(int & x, int & y, int a, int b, int cnt) {
    x += cnt * b;
    y -= cnt * a;
}

int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
    int x, y, g;
    if (!find_any_solution(a, b, c, x, y, g))
        return 0;
    a /= g;
    b /= g;

    int sign_a = a > 0 ? +1 : -1;
    int sign_b = b > 0 ? +1 : -1;

    shift_solution(x, y, a, b, (minx - x) / b);
    if (x < minx)
        shift_solution(x, y, a, b, sign_b);
    if (x > maxx)
        return 0;
    int lx1 = x;

    shift_solution(x, y, a, b, (maxx - x) / b);
    if (x > maxx)
        shift_solution(x, y, a, b, -sign_b);
    int rx1 = x;

    shift_solution(x, y, a, b, -(miny - y) / a);
    if (y < miny)
        shift_solution(x, y, a, b, -sign_a);
    if (y > maxy)
        return 0;
    int lx2 = x;

    shift_solution(x, y, a, b, -(maxy - y) / a);
    if (y > maxy)
        shift_solution(x, y, a, b, sign_a);
    int rx2 = x;

    if (lx2 > rx2)
        swap(lx2, rx2);
    int lx = max(lx1, lx2);
    int rx = min(rx1, rx2);

    if (lx > rx)
        return 0;
    return (rx - lx) / abs(b) + 1;
}

$l_x$ ба $r_x$-г олсны дараа бүх шийдийг жагсаах нь бас энгийн. Зөвхөн $x = r_x$ болтол бүх $k \ge 0$-ийн хувьд $x = l_x + k \cdot \frac{b}{g}$-ээр давтаж, $a x + b y = c$ тэгшитгэл ашиглан харгалзах $y$ утгуудыг олоход хангалттай.

$x + y$-ийн хамгийн бага утгатай шийдийг олох¶

Энд $x$ ба $y$-д бас зарим хязгаарлалт өгөх шаардлагатай, эс тэгвээс хариу хасах хязгааргүй болж магадгүй.

Санаа нь өмнөх хэсэгтэй адил: бид Диофантын тэгшитгэлийн дурын шийдийг олоод, дараа нь зарим нөхцөлийг хангахаар шийдийг шилжүүлнэ.

Эцэст нь бүх шийдийн олонлогийн талаарх мэдлэгээ ашиглан хамгийн багыг олно:

$$x' = x + k \cdot \frac{b}{g},$$

$$y' = y - k \cdot \frac{a}{g}.$$

$x + y$ дараах байдлаар өөрчлөгдөхийг анхаараарай:

$$x' + y' = x + y + k \cdot \left(\frac{b}{g} - \frac{a}{g}\right) = x + y + k \cdot \frac{b-a}{g}$$

Хэрэв $a < b$ бол бид $k$-гийн хамгийн бага боломжит утгыг сонгох хэрэгтэй. Хэрэв $a > b$ бол $k$-гийн хамгийн их боломжит утгыг сонгоно. Хэрэв $a = b$ бол бүх шийд ижил $x + y$ нийлбэртэй байна.