Dados dos enteros positivos ‘a’ y ‘b’ que representan coeficientes en la ecuación ax + by = m. Encuentre el valor mínimo de m que satisfaga la ecuación para cualquier valor entero positivo de x e y. Y después de este valor mínimo, la ecuación es satisfecha por todos los valores (mayores) de m. Si no existe tal valor mínimo, devuelva «-1».
Ejemplos:
Input: a = 4, b = 7
Output: 18
Explanation: 18 is the smallest value that
can be satisfied by equation 4x + 7y.
4*1 + 7*2 = 18
And after 18 all values are satisfied
4*3 + 7*1 = 19
4*5 + 7*0 = 20
... and so on.
Esta es una variación del problema de la moneda de Frobenius . En el problema de la moneda de Frobenius, necesitamos encontrar el número más grande que no se puede representar usando dos monedas. La mayor cantidad de monedas con denominaciones como ‘a’ y ‘b’ es a*b – (a+b). Entonces, el número más pequeño que se puede representar usando dos monedas y todos los números posteriores también se pueden representar es a*b – (a+b) + 1. Un caso importante es
cuando MCD de ‘a’ y ‘b’ no es 1. Por ejemplo, si ‘a’ = 4 y ‘b’ = 6, entonces todos los valores que pueden representarse usando dos monedas son pares (o todos los valores de m que pueden estratificar la ecuación) son pares. Entonces todos los valores que NO son múltiplos de 2, no pueden satisfacer la ecuación. En este caso no existe un valor mínimo a partir del cual todos los valores satisfagan la ecuación.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find the minimum value of m that satisfies
// ax + by = m and all values after m also satisfy
#include<bits/stdc++.h>
using namespace std;
int findMin(int a, int b)
{
// If GCD is not 1, then there is no such value,
// else value is obtained using "a*b-a-b+1'
return (__gcd(a, b) == 1)? a*b-a-b+1 : -1;
}
// Driver code
int main()
{
int a = 4, b = 7;
cout << findMin(a, b) << endl;
return 0;
}
Java
// Java program to find the
// minimum value of m that
// satisfies ax + by = m
// and all values after m
// also satisfy
import java.io.*;
class GFG
{
// Recursive function to
// return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0 && b == 0)
return 0;
// base case
if (a == b)
return a;
// a is greater$
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
static int findMin( int a, int b)
{
// If GCD is not 1, then
// there is no such value,
// else value is obtained
// using "a*b-a-b+1'
return (__gcd(a, b) == 1)?
a * b - a - b + 1 : -1;
}
// Driver code
public static void main (String[] args)
{
int a = 4;
int b = 7;
System.out.println(findMin(a, b));
}
}
// This code is contributed
// by akt_mit
Python3
# Python3 program to find the minimum # value of m that satisfies ax + by = m # and all values after m also satisfy # Recursive function to return # gcd of a and b def __gcd(a, b): # Everything divides 0 if (a == 0 or b == 0): return 0; # base case if (a == b): return a; # a is greater if (a > b): return __gcd(a - b, b); return __gcd(a, b - a); def findMin( a, b): # If GCD is not 1, then # there is no such value, # else value is obtained # using "a*b-a-b+1' if(__gcd(a, b) == 1): return (a * b - a - b + 1) else: return -1 # Driver code a = 4; b = 7; print(findMin(a, b)); # This code is contributed by mits
C#
// C# program to find the minimum
// value of m that satisfies
// ax + by = m and all values
// after m also satisfy
class GFG
{
// Recursive function to
// return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0 && b == 0)
return 0;
// base case
if (a == b)
return a;
// a is greater$
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
static int findMin( int a, int b)
{
// If GCD is not 1, then
// there is no such value,
// else value is obtained
// using "a*b-a-b+1'
return (__gcd(a, b) == 1)?
a * b - a - b + 1 : -1;
}
// Driver code
public static void Main()
{
int a = 4;
int b = 7;
System.Console.WriteLine(findMin(a, b));
}
}
// This code is contributed
// by mits
PHP
<?php
// PHP program to find the
// minimum value of m that
// satisfies ax + by = m
// and all values after m
// also satisfy
// Recursive function to
// return gcd of a and b
function __gcd($a, $b)
{
// Everything divides 0
if ($a == 0 or $b == 0)
return 0;
// base case
if ($a == $b)
return $a;
// a is greater$
if ($a > $b)
return __gcd($a - $b, $b);
return __gcd($a, $b - $a);
}
function findMin( $a, $b)
{
// If GCD is not 1, then
// there is no such value,
// else value is obtained
// using "a*b-a-b+1'
return (__gcd($a, $b) == 1)?
$a * $b - $a - $b + 1 : -1;
}
// Driver code
$a = 4; $b = 7;
echo findMin($a, $b) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program
// to find the minimum
// value of m that satisfies
// ax + by = m and all values
// after m also satisfy
// Recursive function to
// return gcd of a and b
function __gcd(a, b)
{
// Everything divides 0
if (a == 0 && b == 0)
return 0;
// base case
if (a == b)
return a;
// a is greater$
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
function findMin(a, b)
{
// If GCD is not 1, then
// there is no such value,
// else value is obtained
// using "a*b-a-b+1'
return (__gcd(a, b) == 1)?
a * b - a - b + 1 : -1;
}
let a = 4;
let b = 7;
document.write(findMin(a, b));
</script>
Producción:
18
Complejidad de tiempo: O(log(min(a, b)), donde a y b son los dos enteros dados.
Espacio auxiliar: O(1), no se requiere espacio extra por lo que es una constante.
Este artículo es una contribución de Rishabh Jain . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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