Una ecuación diofántica es una ecuación polinomial, generalmente con dos o más incógnitas, de modo que solo se requieren las soluciones integrales. Una solución integral es una solución tal que todas las variables desconocidas toman solo valores enteros.
Dados tres enteros a, b, c que representan una ecuación lineal de la forma: ax + by = c. Determina si la ecuación tiene una solución tal que x e y sean ambos valores integrales.
Ejemplos:
Input : a = 3, b = 6, c = 9 Output: Possible Explanation : The Equation turns out to be, 3x + 6y = 9 one integral solution would be x = 1 , y = 1 Input : a = 3, b = 6, c = 8 Output : Not Possible Explanation : o integral values of x and y exists that can satisfy the equation 3x + 6y = 8 Input : a = 2, b = 5, c = 1 Output : Possible Explanation : Various integral solutions possible are, (-2,1) , (3,-1) etc.
Solución:
Para las ecuaciones de ecuaciones diofánticas lineales, existen soluciones integrales si y solo si, el MCD de los coeficientes de las dos variables divide perfectamente el término constante. En otras palabras, la solución integral existe si MCD(a,b) divide a c.
Por lo tanto, el algoritmo para determinar si una ecuación tiene solución integral es bastante sencillo.
- Encuentra el MCD de a y b
- Comprobar si c % GCD(a,b) ==0
- En caso afirmativo, imprima Posible
- De lo contrario, imprimir No es posible
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to check for solutions of diophantine
// equations
#include <bits/stdc++.h>
using namespace std;
//utility function to find the GCD of two numbers
int gcd(int a, int b)
{
return (a%b == 0)? abs(b) : gcd(b,a%b);
}
// This function checks if integral solutions are
// possible
bool isPossible(int a, int b, int c)
{
return (c%gcd(a,b) == 0);
}
//driver function
int main()
{
// First example
int a = 3, b = 6, c = 9;
isPossible(a, b, c)? cout << "Possible\n" :
cout << "Not Possible\n";
// Second example
a = 3, b = 6, c = 8;
isPossible(a, b, c)? cout << "Possible\n" :
cout << "Not Possible\n";
// Third example
a = 2, b = 5, c = 1;
isPossible(a, b, c)? cout << "Possible\n" :
cout << "Not Possible\n";
return 0;
}
Java
// Java program to check for solutions of
// diophantine equations
import java.io.*;
class GFG {
// Utility function to find the GCD
// of two numbers
static int gcd(int a, int b)
{
return (a % b == 0) ?
Math.abs(b) : gcd(b,a%b);
}
// This function checks if integral
// solutions are possible
static boolean isPossible(int a,
int b, int c)
{
return (c % gcd(a, b) == 0);
}
// Driver function
public static void main (String[] args)
{
// First example
int a = 3, b = 6, c = 9;
if(isPossible(a, b, c))
System.out.println( "Possible" );
else
System.out.println( "Not Possible");
// Second example
a = 3; b = 6; c = 8;
if(isPossible(a, b, c))
System.out.println( "Possible") ;
else
System.out.println( "Not Possible");
// Third example
a = 2; b = 5; c = 1;
if(isPossible(a, b, c))
System.out.println( "Possible" );
else
System.out.println( "Not Possible");
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program to check for solutions
# of diophantine equations
from math import gcd
# This function checks if integral
# solutions are possible
def isPossible(a, b, c):
return (c % gcd(a, b) == 0)
# Driver Code
if __name__ == '__main__':
# First example
a = 3
b = 6
c = 9
if (isPossible(a, b, c)):
print("Possible")
else:
print("Not Possible")
# Second example
a = 3
b = 6
c = 8
if (isPossible(a, b, c)):
print("Possible")
else:
print("Not Possible")
# Third example
a = 2
b = 5
c = 1
if (isPossible(a, b, c)):
print("Possible")
else:
print("Not Possible")
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to check for
// solutions of diophantine
// equations
using System;
class GFG
{
// Utility function to find
// the GCD of two numbers
static int gcd(int a, int b)
{
return (a % b == 0) ?
Math.Abs(b) :
gcd(b, a % b);
}
// This function checks
// if integral solutions
// are possible
static bool isPossible(int a,
int b,
int c)
{
return (c % gcd(a, b) == 0);
}
// Driver Code
public static void Main ()
{
// First example
int a = 3, b = 6, c = 9;
if(isPossible(a, b, c))
Console.WriteLine("Possible");
else
Console.WriteLine("Not Possible");
// Second example
a = 3; b = 6; c = 8;
if(isPossible(a, b, c))
Console.WriteLine("Possible") ;
else
Console.WriteLine("Not Possible");
// Third example
a = 2; b = 5; c = 1;
if(isPossible(a, b, c))
Console.WriteLine("Possible");
else
Console.WriteLine("Not Possible");
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to check for solutions of
// diophantine equations
// utility function to find the
// GCD of two numbers
function gcd($a, $b)
{
return ($a % $b == 0) ?
abs($b) : gcd($b, $a % $b);
}
// This function checks if integral
// solutions are possible
function isPossible($a, $b, $c)
{
return ($c % gcd($a, $b) == 0);
}
// Driver Code
// First example
$a = 3;
$b = 6;
$c = 9;
if(isPossible($a, $b, $c) == true)
echo "Possible\n" ;
else
echo "Not Possible\n";
// Second example
$a = 3;
$b = 6;
$c = 8;
if(isPossible($a, $b, $c) == true)
echo "Possible\n" ;
else
echo "Not Possible\n";
// Third example
$a = 2;
$b = 5;
$c = 1;
if(isPossible($a, $b, $c) == true)
echo "Possible\n" ;
else
echo "Not Possible\n";
// This code is contributed by ajit..
?>
Javascript
<script>
// Javascript program to check for solutions of
// diophantine equations
// Utility function to find the GCD
// of two numbers
function gcd(a, b)
{
return (a % b == 0) ?
Math.abs(b) : gcd(b,a%b);
}
// This function checks if integral
// solutions are possible
function isPossible(a,
b, c)
{
return (c % gcd(a, b) == 0);
}
// Driver Code
// First example
let a = 3, b = 6, c = 9;
if(isPossible(a, b, c))
document.write( "Possible" + "<br/>" );
else
document.write( "Not Possible" + "<br/>" );
// Second example
a = 3; b = 6; c = 8;
if(isPossible(a, b, c))
document.write( "Possible" + "<br/>" ) ;
else
document.write( "Not Possible" + "<br/>" );
// Third example
a = 2; b = 5; c = 1;
if(isPossible(a, b, c))
document.write( "Possible" + "<br/>" );
else
document.write( "Not Possible" + "<br/>" );
</script>
Producción :
Possible Not Possible Possible
¿Como funciona esto?
Sea MCD de ‘a’ y ‘b’ ‘g’. g divide a y b. Esto implica que g también divide (ax + by) (si xey son números enteros). Esto implica que gcd también divide ‘c’ usando la relación ax + by = c. Consulte este enlace wiki para obtener más detalles.
Este artículo es una contribución de Ashutosh Kumar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA