OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Ecuaciones Diofánticas Lineales =====

Las ecuaciones diofánticas lineales son las expresiones $A*x + B*y = C$, donde $A, B, C$ son números enteros dados, y $x, y$ son las variables enteras que hay que encontrar. El lema llamado "Lema de Bézout" afirma que el sistema tiene solución si y sólo si $d = mcd(A, B)$ divide a $C$. Esto suele verse como que el menor número positivo $C$ para el cual existe solución es $C=mcd(A, B)$. Y a partir de ahí, si tenemos $(x,y)$ tales que $A*x + B*y = d$, y $C=k*d$, luego $A*x*k + B*y*k = d*k = C$, y tendremos que $(x*k, y*k)$ será solución del sistema inicial.

Entonces a partir de ahora vamos a tratar el problema $A*x + B*y = mcd(A, B) = d$, y luego sabemos como llevar las soluciones de este sistema a las de uno con $C=k*d$ para cualquier $k$ entero.

===== Infinitas soluciones =====

Veamos que si existe solución, existen infinitas soluciones:

Supongamos que tenemos $(x,y)$ solución del sistema. Sea $k$ un entero cualquiera, veamos que $(x+k*\frac{B}{mcd(A,B)}, y-k*\frac{A}{mcd(A,B)})$ es solución:

$ A*(x+k*\frac{B}{mcd(A,B)}) + B*(y-k*\frac{A}{mcd(A,B)}) = $
$A*x + A*k*\frac{B}{mcd(A,B)} + B*y - B*k*\frac{A}{mcd(A,B)} = A*x + B*y = d $

Como esto se cumple para cualquier $k$ entero, hay infinitas soluciones.

Esto de encontrar soluciones a partir de otras es **súper útil**, porque hay problemas que podemos necesitar una solución en la que ambas $x$ e $y$ sean positivas, como por ejemplo si quisiéramos pagar un precio $d$ con monedas de valores $A$ y $B$, usando por lo menos una moneda de cada valor. En ese caso, puede que nuestro algoritmo encuentre una solución con alguno de los valores negativos, pero luego usamos esta fórmula para buscar (si es que existe) una solución con ambos valores positivos.

===== Encontrar una solución =====

Para encontrar una solución, se aprovecha el algoritmo de Euclides mencionado en el post de [[:algoritmos-oia:enteros:maximo-comun-divisor|MCD]].

Supongamos que $A = B*q_1 + r_1$. Luego, debemos calcular $mcd(B, r_1)$:
$B = r_1*q_2 + r_2$
$r_1 = r_2*q_3 + r_3$
$...$
$r_{t-3} = r_{t-2}*q_{t-1} + r_{t-1}$
$r_{t-2} = r_{t-1}*q_{t} + r_{t}$
$r_{t-1} = r_t*q_{t+1}$

Acá, $r_t = mcd(A,B) = d$.
Una vez llegado al final, vamos reconstruyendo:
$r_{t-2}-r_{t-1}*q_t = d$

Substituyendo de la antepenúltima ecuación el valor de $r_{t-1}$:
$r_{t-2} - (r_{t-3} - r_{t-2}*q_{t-1})*q_t = d$

Y así seguimos, [[:algoritmos-oia:recursion|recursivamente]], hasta encontrar los valores de $x$ e $y$.


===== Código =====

El mejor código que conozco de esto y que voy a transcribir acá es de una [[http://trainingcamp.org.ar/actual/clases/08-primalidad.pdf|clase]] de Pablo Blanc dictada en el Training Camp 2017, en la parte en la que habla de MCD. Usa **struct**, que se puede leer [[http://wiki.oia.unsam.edu.ar/curso-cpp/struct|acá]].

Hay muchos códigos en internet para resolver este tipo de ecuaciones pero la mayoría usa punteros (algo que ni siquiera es tan necesario de saber).

<code cpp>

struct dxy {
    long long int d,x,y;
};

dxy mcde(long long int a, long long int b) {
    dxy r, t;
    if (b == 0) {
        r.d = a;
        r.x = 1;
        r.y = 0;
    } else {
        t = mcde(b, a%b);
        r.d = t.d;
        r.x = t.y;
        r.y = t.x - a/b*t.y;
    }
    return r;
}

</code>

Así, entonces, haciendo

<code cpp>
dxy ans = mcde(20, 35);
cout<<"20*("<<ans.x<<") + 35*("<<ans.y<<") = "<<ans.d<<endl;
</code>
obtenemos: **20*(2) + 35*(-1) = 5**, donde $5$ es $mcd(20, 35)$.
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
