Hacer dos números iguales en como máximo K pasos dividiendo por su factor

Dados los números enteros X, Y y K, la tarea es hacer que X e Y sean iguales en no más de K operaciones aplicando las siguientes operaciones:

• Elige un entero A y haz que X = X/A, (donde A es un entero que es mayor que 1 y no igual a X).
• Elija un número entero A y haga Y = Y/A, (donde A es un número entero que es mayor que 1 y no igual a Y).

Ejemplos:

Entrada: X = 10, Y = 20, K = 4
Salida: SÍ
Explicación: Una solución óptima para hacerlos iguales es:
Primero elige A = 2 y haz X = X/2, así que ahora X es igual a 5.
Ahora elige A = 4 y hacer Y = Y/4, entonces ahora Y es igual a 5.
Ya que hemos aplicado solo dos operaciones aquí, que es menor que K 
para hacer que X e Y sean iguales y también mayores que uno.
Por lo tanto la respuesta es SÍ.

Entrada: X = 2, Y = 27, K = 1
Salida: NO
Explicación: No hay forma posible de hacer que X e Y sean iguales 
en una operación menor o igual a 1.

Enfoque: Para resolver el problema, siga la siguiente idea:

Aquí hay sólo dos casos posibles:

• Cuando K es igual a uno y 
• Cuando K es mayor que 1

Si K es igual a uno, entonces es posible hacer que X e Y sean iguales solo cuando X es divisible por Y o Y es divisible por X

Si K es mayor que 1, entonces X e Y pueden ser iguales y mayores que 1 solo cuando su GCD es mayor que 1.

Siga los pasos mencionados a continuación para implementar la idea:

• Compruebe si K = 1:
  • En ese caso, averigua si alguno de ellos es divisor del otro.
• De lo contrario, encuentra el MCD de los números.
  • Si el GCD es 1, entonces no es posible.
  • De lo contrario, siempre existe una respuesta.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check the possibility of the answer
bool isPossible(int X, int Y, int K)
{
    // Case 1: when k=1
    if (K == 1) {
        if (X % Y == 0 || Y % X == 0)
            return true;
        return false;
    }
 
    // Case 2: when k>1
    else {
        if (__gcd(X, Y) > 1)
            return true;
        return false;
    }
    return false;
}
 
// Driver code
int main()
{
    int X = 10;
    int Y = 20;
    int K = 4;
 
    // Function call
    bool answer = isPossible(X, Y, K);
    if (answer)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

// Java code to implement the approach
 
public class GFG {
     
   // Recursive function to return gcd of a and b
    static int gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
          return b;
        if (b == 0)
          return a;
       
        // base case
        if (a == b)
            return a;
       
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
     
    // Function to check the possibility of the answer
    static boolean isPossible(int X, int Y, int K)
    {
        // Case 1: when k=1
        if (K == 1) {
            if (X % Y == 0 || Y % X == 0)
                return true;
            return false;
        }
     
        // Case 2: when k>1
        else {
            if (gcd(X, Y) > 1)
                return true;
            return false;
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int X = 10;
        int Y = 20;
        int K = 4;
     
        // Function call
        boolean answer = isPossible(X, Y, K);
        if (answer == true)
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
 
// This code is contributed by AnkThon

# Python3 code to implement the approach
import math
 
# Function to check the possibility of the answer
def isPossible(X, Y, K):
     
    # Case 1: when k=1
    if (K == 1) :
        return (X % Y == 0 or Y % X == 0)
 
    # Case 2: when k>1
    else :
        return (math.gcd(X, Y) > 1)
 
    return False
 
# Driver code
X, Y, K = 10, 20, 4
 
# Function call
answer = isPossible(X, Y, K);
 
if (answer):
    print("YES")
else:
    print("NO")
 
# This code is contributed by phasing17

// C# code to implement the approach
using System;
 
public class GFG {
     
   // Recursive function to return gcd of a and b
    static int gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
          return b;
        if (b == 0)
          return a;
       
        // base case
        if (a == b)
            return a;
       
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
     
    // Function to check the possibility of the answer
    static bool isPossible(int X, int Y, int K)
    {
        // Case 1: when k=1
        if (K == 1) {
            if (X % Y == 0 || Y % X == 0)
                return true;
            return false;
        }
     
        // Case 2: when k>1
        else {
            if (gcd(X, Y) > 1)
                return true;
            return false;
        }
    }
     
    // Driver code
    public static void Main (string[] args)
    {
        int X = 10;
        int Y = 20;
        int K = 4;
     
        // Function call
        bool answer = isPossible(X, Y, K);
        if (answer == true)
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}
 
// This code is contributed by AnkThon

<script>
//Javascript code to implement the approach
function _gcd(a,b){
   if(b==0)
     return a;
     return _gcd(b,a%b);
}
 
// Function to check the possibility of the answer
function isPossible(X, Y, K)
{
    // Case 1: when k=1
    if (K == 1) {
        if (X % Y == 0 || Y % X == 0)
            return true;
        return false;
    }
 
    // Case 2: when k>1
    else {
        if (_gcd(X, Y) > 1)
            return true;
        return false;
    }
    return false;
}
 
// Driver code
 
    let X = 10;
    let Y = 20;
    let K = 4;
 
    // Function call
    let answer = isPossible(X, Y, K);
    if (answer)
        document.write("YES","</br>")
    else
        document.write("NO","</br>")
         
        // This code is contributed by satwik4409.
    </script>

YES

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)