Equação Diofantina Linear

Uma Equação Diofantina Linear (em duas variáveis) é uma equação da forma geral:

$$ax + by = c$$

onde $a$, $b$, $c$ são inteiros dados, enquanto $x$ e $y$ são inteiros desconhecidos.

Neste artigo, consideramos vários problemas clássicos sobre essas equações:

Caso degenerado

Um caso degenerado que precisa ser resolvido é quando $a = b = 0$. É fácil ver que não temos soluções ou infinitas soluções, dependendo se $c = 0$ ou não. No resto deste artigo, ignoraremos esse caso.

Encontrando uma solução

Para encontrar uma solução da equação diofantina com 2 incógnitas, você pode usar o algoritmo de euclides estendido. Primeiro, suponha que $a$ e $b$ são não-negativos. Quando aplicamos o algoritmo de euclides para $a$ e $b$, podemos encontrar o máximo divisor comum $g$ e 2 números $x_g$ e $y_g$ de modo que:

$$a x_g + b y_g = g$$

Se $c$ é divisível por $g = \gcd(a, b)$, então a equação diofantina dada tem uma solução, caso contrário, ela não tem solução. A prova é direta: uma combinação linear de dois números é divisível pelo seu divisor comum.

Agora suponha que $c$ seja divisível por $g$, então temos:

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

Portanto, uma das soluções da equação diofantina é:

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

A idéia acima ainda funciona quando $a$ ou $b$ ou ambos são negativos. Só precisamos alterar o sinal de $x_0$ e $y_0$ quando necessário.

Por fim, podemos implementar essa ideia da seguinte maneira (esse código não considera o caso $a = b = 0$):

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

bool find_sol(int a, int b, int c, int &x0, int &y0, int &g) {   //encontra qualquer solução
    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;
}

Obtendo todas as soluções

A partir de uma solução $(x_0, y_0)$, podemos obter todas as soluções da equação dada.

Seja $g = \gcd(a, b)$ e seja $x_0, y_0$ números inteiros que satisfaçam o seguinte:

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

Agora, devemos ver que adicionar $b / g$ to $x_0$, e, ao mesmo tempo, subtrair $a / g$ de $y_0$ não quebrará a igualdade:

$$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$$

Obviamente, esse processo pode ser repetido novamente, portanto, todos os números da forma:

$$x = x_0 + k \cdot \frac{b}{g}$$ $$y = y_0 - k \cdot \frac{a}{g}$$

são soluções da equação diofantina dada.

Além disso, este é o conjunto de todas as soluções possíveis da equação diofantina dada.

Encontrando o número de soluções e as soluções em um determinado intervalo

Na seção anterior, deve ficar claro que, se não impormos restrições às soluções, haverá um número infinito delas. Portanto, nesta seção, adicionamos algumas restrições no intervalo de $x$ e $y$, e tentaremos contar e enumerar todas as soluções.

Sejam dois intervalos: $[min_x; max_x]$ e $[min_y; max_y]$, digamos que queremos apenas encontrar as soluções nesses dois intervalos.

Observe que se $a$ ou $b$ é $0$, o problema terá apenas uma solução. Não consideramos esse caso aqui.

Primeiro, podemos encontrar uma solução que tenha um valor mínimo de $x$, tal que $x \ge min_x$. Para fazer isso, primeiro encontramos qualquer solução da equação diofantina. Em seguida, alteramos essa solução para obter $x \ge min_x$ (usando o que sabemos sobre o conjunto de todas as soluções na seção anterior). Isso pode ser feito em $O(1)$. Denote esse mínimo valor de $x$ como $l_{x1}$.

Da mesma forma, podemos encontrar o valor máximo de $x$ que satisfaça $x \le max_x$. Indique esse valor máximo de $x$ como $r_{x1}$.

Da mesma forma, podemos encontrar o valor mínimo de $y$ $(y \ge min_y)$ e valores máximos de $y$ $(y \le max_y)$. Indique os valores correspondentes de $x$ como $l_{x2}$ e $r_{x2}$.

A solução final são todas as soluções com x na interseção de $[l_{x1}, r_{x1}]$ e $[l_{x2}, r_{x2}]$. Iremos denotar essa interseção como $[l_x, r_x]$.

A seguir, está o código que implementa essa ideia. Observe que dividimos $a$ e $b$ no início por $g$. Como a equação $a x + b y = c$ é equivalente à equação $\frac{a}{g} x + \frac{b}{g} y = \frac{c}{g}$, podemos usar essa e ter $\gcd(\frac{a}{g}, \frac{b}{g}) = 1$, o que simplifica as fórmulas.

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;
}

Depois de temos $l_x$ e $r_x$, podemos enumerar todas as soluções. É necessário iterar através de $x = l_x + k \cdot \frac{b}{g}$ para todo $k \ge 0$ até que $x = r_x$, e encontrar os valores correspondentes de $y$ usando a equação $a x + b y = c$.

Encontre a solução com o valor mínimo de $x + y$

Aqui, $x$ e $y$ também precisam receber alguma restrição, caso contrário, a resposta pode se tornar infinito negativo.

A idéia é semelhante à seção anterior: Encontramos qualquer solução da equação diofantina e depois alteramos a solução para satisfazer algumas condições.

Por fim, use o conhecimento do conjunto de todas as soluções para encontrar o mínimo:

$$x' = x + k \cdot \frac{b}{g},$$ $$y' = y - k \cdot \frac{a}{g}.$$

Note que $x + y$ mudam da seguinte maneira:

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

Se $a < b$, precisamos selecionar o menor valor possível de $k$. Se $a > b$, precisamos selecionar o maior valor possível de $k$. Se $a = b$, todas as soluções terão a mesma soma $x + y$.

Problemas