Encuentre la solución integral inicial de la ecuación diofántica lineal si existe una solución finita

Dados tres enteros a , b y c que representan una ecuación lineal de la forma: ax + by = c . La tarea es encontrar la solución integral inicial de la ecuación dada si existe una solución finita.

Una ecuación diofántica lineal (LDE) es una ecuación con 2 o más incógnitas enteras y cada una de las incógnitas enteras tiene un grado máximo de 1. La ecuación diofántica lineal en dos variables toma la forma de ax+by=c, donde x,y son variables enteras y a, b, c son constantes enteras. x e y son variables desconocidas.

Ejemplos: 

Entrada: a = 4, b = 18, c = 10 
Salida: x = -20, y = 5 
 

Explicación: (-20)*4 + (5)*18 = 10

Entrada: a = 9, b = 12, c = 5 
Salida: No existe ninguna solución 
 

Acercarse: 

1. Primero, verifique si a y b son distintos de cero.
2. Si ambos son cero y c es distinto de cero, entonces no existe solución. Si c también es cero, entonces existe una solución infinita.
3. Para dados a y b , calcule el valor de x ₁ , y ₁ y mcd usando el Algoritmo Euclidiano Extendido .
4. Ahora, para una solución a gcd(a, b) existente debe ser múltiplo de c .
5. Calcular la solución de la ecuación de la siguiente manera:

x = x1 * ( c / gcd )
y = y1 * ( c / gcd )

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement the extended
// euclid algorithm
int gcd_extend(int a, int b,
               int& x, int& y)
{
    // Base Case
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else {
        int g = gcd_extend(b,
                           a % b, x, y);
        int x1 = x, y1 = y;
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
void print_solution(int a, int b, int c)
{
    int x, y;
    if (a == 0 && b == 0) {
 
        // Condition for infinite solutions
        if (c == 0) {
            cout
                << "Infinite Solutions Exist"
                << endl;
        }
 
        // Condition for no solutions exist
        else {
            cout
                << "No Solution exists"
                << endl;
        }
    }
    int gcd = gcd_extend(a, b, x, y);
 
    // Condition for no solutions exist
    if (c % gcd != 0) {
        cout
            << "No Solution exists"
            << endl;
    }
    else {
 
        // Print the solution
        cout << "x = " << x * (c / gcd)
             << ", y = " << y * (c / gcd)
             << endl;
    }
}
 
// Driver Code
int main(void)
{
    int a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function Call
    print_solution(a, b, c);
    return 0;
}

// Java program for the above approach
class GFG{
 
static int x, y;
 
// Function to implement the extended
// euclid algorithm
static int gcd_extend(int a, int b)
{
     
    // Base Case
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else
    {
        int g = gcd_extend(b, a % b);
        int x1 = x, y1 = y;
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
static void print_solution(int a, int b, int c)
{
    if (a == 0 && b == 0)
    {
         
        // Condition for infinite solutions
        if (c == 0)
        {
            System.out.print("Infinite Solutions " +
                             "Exist" + "\n");
        }
 
        // Condition for no solutions exist
        else
        {
            System.out.print("No Solution exists" +
                             "\n");
        }
    }
    int gcd = gcd_extend(a, b);
 
    // Condition for no solutions exist
    if (c % gcd != 0)
    {
        System.out.print("No Solution exists" + "\n");
    }
    else
    {
         
        // Print the solution
        System.out.print("x = " + x * (c / gcd) +
                       ", y = " + y * (c / gcd) + "\n");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function Call
    print_solution(a, b, c);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
import math
 
x, y = 0, 0
   
# Function to implement the extended
# euclid algorithm
def gcd_extend(a, b):
    global x, y
     
    # Base Case
    if (b == 0):
        x = 1
        y = 0
        return a
   
    # Recursively find the gcd
    else:
        g = gcd_extend(b, a % b)
        x1, y1 = x, y
        x = y1
        y = x1 - math.floor(a / b) * y1
        return g
   
# Function to print the solutions of
# the given equations ax + by = c
def print_solution(a, b, c):
    if (a == 0 and b == 0):
       
        # Condition for infinite solutions
        if (c == 0):
            print("Infinite Solutions Exist")
   
        # Condition for no solutions exist
        else :
            print("No Solution exists")
    gcd = gcd_extend(a, b)
   
    # Condition for no solutions exist
    if (c % gcd != 0):
        print("No Solution exists")
    else:
        # Print the solution
        print("x = ", int(x * (c / gcd)), ", y = ", int(y * (c / gcd)), sep = "")
         
# Given coefficients
a = 4
b = 18
c = 10
 
# Function Call
print_solution(a, b, c)
 
# This code is contributed by decode2207.

// C# program for the above approach
using System;
 
class GFG{
 
static int x, y;
 
// Function to implement the extended
// euclid algorithm
static int gcd_extend(int a, int b)
{
     
    // Base Case
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else
    {
        int g = gcd_extend(b, a % b);
        int x1 = x, y1 = y;
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
static void print_solution(int a, int b, int c)
{
    if (a == 0 && b == 0)
    {
         
        // Condition for infinite solutions
        if (c == 0)
        {
            Console.Write("Infinite Solutions " +
                          "Exist" + "\n");
        }
 
        // Condition for no solutions exist
        else
        {
            Console.Write("No Solution exists" +
                          "\n");
        }
    }
    int gcd = gcd_extend(a, b);
 
    // Condition for no solutions exist
    if (c % gcd != 0)
    {
        Console.Write("No Solution exists" + "\n");
    }
    else
    {
         
        // Print the solution
        Console.Write("x = " + x * (c / gcd) +
                    ", y = " + y * (c / gcd) + "\n");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function call
    print_solution(a, b, c);
}
}
 
// This code contributed by amal kumar choubey

<script>
 
// Javascript program for the above approach
  
let x, y;
 
// Function to implement the extended
// euclid algorithm
function gcd_extend(a, b)
{
     
    // Base Case
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
 
    // Recursively find the gcd
    else
    {
        let g = gcd_extend(b, a % b);
        let x1 = x, y1 = y;
        x = y1;
        y = x1 - Math.floor(a / b) * y1;
        return g;
    }
}
 
// Function to print the solutions of
// the given equations ax + by = c
function print_solution(a, b, c)
{
    if (a == 0 && b == 0)
    {
         
        // Condition for infinite solutions
        if (c == 0)
        {
            document.write("Infinite Solutions " +
                             "Exist" + "\n");
        }
 
        // Condition for no solutions exist
        else
        {
            document.write("No Solution exists" +
                             "\n");
        }
    }
    let gcd = gcd_extend(a, b);
 
    // Condition for no solutions exist
    if (c % gcd != 0)
    {
        document.write("No Solution exists" + "\n");
    }
    else
    {
         
        // Print the solution
        document.write("x = " + x * (c / gcd) +
                       ", y = " + y * (c / gcd) + "<br/>");
    }
}
 
// Driver Code
     
   let a, b, c;
 
    // Given coefficients
    a = 4;
    b = 18;
    c = 10;
 
    // Function Call
    print_solution(a, b, c);
         
</script>

x = -20, y = 5

Complejidad de tiempo: O(log(max(A, B))) , donde A y B son el coeficiente de xey en la ecuación lineal dada. 
Espacio Auxiliar: O(1)