Compruebe si es posible llegar a (X, Y) desde (1, 0) siguiendo los pasos dados

Dados dos enteros positivos X e Y , la tarea es verificar si es posible llegar a (X, Y) desde (1, 0) mediante los pasos dados. En cada paso, los movimientos posibles desde cualquier celda (a, b) son (a, b + a) o (a + b, b) . Escriba “Sí” si es posible. De lo contrario, escriba “No” .

Ejemplos:

Entrada: X = 2, Y = 7
Salida: Sí
Explicación: La secuencia de movimientos para alcanzar (2, 7) es: (1, 0) -> (1, 1) -> (2, 1) -> (2, 3) -> (2, 5) -> (2, 7).

Entrada: X = 30, Y = 24
Salida: No

Enfoque ingenuo: el enfoque más simple es tratar de pasar de los puntos (X, Y) a (1, 0) recursivamente usando la operación (X – Y, Y) o (X, Y – X) hasta que sea igual a ( 1, 0) . Si la coordenada X se vuelve menor que 1 o la coordenada Y se vuelve menor que 0 , entonces no es posible llegar a (1, 0) . Por lo tanto, escriba “No” . De lo contrario, si se alcanza (1, 0) , escriba «Sí» . 

Complejidad de tiempo: O(2 ^{log (min(X, Y))} )
Espacio auxiliar: O(1)

Enfoque Eficiente: La idea es observar las siguientes propiedades:

• Trate de resolver el problema en orden inverso, es decir, es posible pasar de (X, Y) a (1, 0) moviéndose solo a los puntos (X – Y, Y) o (X, Y – X) .
• La propiedad anterior se puede representar de la siguiente manera:

MCD(X, Y) = MCD(X, Y – X) o MCD(X – Y, Y)
donde,  
el caso base es MCD(X, 0) = X
Ahora, observe que mcd de 1 y 0, es decir, mcd( 1, 0) es 1.
Por lo tanto, el mcd de X e Y también debe ser 1 para llegar a (1, 0).

Por lo tanto, a partir de las observaciones anteriores, el camino de (1, 0) a (X, Y) siempre existe si MCD(X, Y) = 1 . Escriba «Sí» si el MCD de los dos números dados es 1 . De lo contrario, escriba “No” .

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

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to find the GCD of two
// numbers a and b
int GCD(int a, int b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively find the GCD
    else
        return GCD(b, a % b);
}
 
// Function to check if (x, y) can be
// reached from (1, 0) from given moves
void check(int x, int y)
{
    // If GCD is 1, then print "Yes"
    if (GCD(x, y) == 1) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}
 
// Driver Code
int main()
{
    // Given X and Y
    int X = 2, Y = 7;
 
    // Function call
    check(X, Y);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class GFG{
 
// Function to find the
// GCD of two numbers a
// and b
static int GCD(int a,
               int b)
{
  // Base Case
  if (b == 0)
    return a;
 
  // Recursively find
  // the GCD
  else
    return GCD(b, a % b);
}
 
// Function to check if
// (x, y) can be reached
// from (1, 0) from given
// moves
static void check(int x,
                  int y)
{
  // If GCD is 1, then
  // print "Yes"
  if (GCD(x, y) == 1)
  {
    System.out.print("Yes");
  }
  else
  {
    System.out.print("No");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  // Given X and Y
  int X = 2, Y = 7;
 
  // Function call
  check(X, Y);
}
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to find the GCD of two
# numbers a and b
def GCD(a, b):
     
    # Base Case
    if (b == 0):
        return a
         
    # Recursively find the GCD
    else:
        return GCD(b, a % b)
 
# Function to check if (x, y) can be
# reached from (1, 0) from given moves
def check(x, y):
     
    # If GCD is 1, then print"Yes"
    if (GCD(x, y) == 1):
        print("Yes")
    else:
        print("No")
 
# Driver Code
if __name__ == '__main__':
     
    # Given X and Y
    X = 2
    Y = 7
 
    # Function call
    check(X, Y)
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
 
class GFG{
   
// Function to find the
// GCD of two numbers a
// and b
static int GCD(int a, int b)
{
   
  // Base Case
  if (b == 0)
    return a;
 
  // Recursively find
  // the GCD
  else
    return GCD(b, a % b);
}
 
// Function to check if
// (x, y) can be reached
// from (1, 0) from given
// moves
static void check(int x, int y)
{
   
  // If GCD is 1, then
  // print "Yes"
  if (GCD(x, y) == 1)
  {
    Console.WriteLine("Yes");
  }
  else
  {
    Console.WriteLine("No");
  }
}
 
// Driver Code
public static void Main()
{
   
  // Given X and Y
  int X = 2, Y = 7;
 
  // Function call
  check(X, Y);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
// JavaScript program for the above approach
 
// Function to find the GCD of two
// numbers a and b
function GCD(a, b)
{
 
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively find the GCD
    else
        return GCD(b, a % b);
}
 
// Function to check if (x, y) can be
// reached from (1, 0) from given moves
function check(x, y)
{
 
    // If GCD is 1, then print "Yes"
    if (GCD(x, y) == 1) {
        document.write("Yes");
    }
    else {
        document.write("No");
    }
}
 
// Driver Code
 
    // Given X and Y
    let X = 2, Y = 7;
 
    // Function call
    check(X, Y);
 
// This code is contributed by Surbhi Tyagi.
</script>

Yes

Complejidad de tiempo: O(log(min(X, Y))
Espacio auxiliar: O(1)