Operaciones mínimas requeridas para convertir X a Y multiplicando X con los coprimos dados

Dados cuatro enteros X , Y , P y Q tales que X ≤ Y y mcd(P, Q) = 1 . La tarea es encontrar la operación mínima requerida para convertir X a Y. En una sola operación, puede multiplicar X con P o Q. Si no es posible convertir X a Y , imprima -1 .
Ejemplos: 
 

Entrada: X = 12, Y = 2592, P = 2, Q = 3 
Salida: 6 
(12 * 2) -> (24 * 3) -> (72 * 2) -> (144 * 3) -> (432 * 3) -> (1296 * 2) ->2592
Entrada: X = 7, Y = 9, P = 2, Q = 7 
Salida: -1 
No hay forma de que podamos llegar a 9 de 7 
multiplicando 7 con 2 o 7 
 

Enfoque: si Y no es divisible por X , entonces ninguna multiplicación integral de cualquier número entero con X puede conducir a Y y el resultado es -1 . 
De lo contrario, sea d = Y/X . Ahora, P ^a * Q ^b = d debe cumplirse para tener una solución válida y el resultado en ese caso será (a + b) sino -1 si d no puede expresarse en las potencias de P y Q . 
Para verificar la condición, siga dividiendo d con P yQ hasta divisible. Ahora, si d = 1 al final, la solución es posible, de lo contrario no.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// operations required
int minOperations(int x, int y, int p, int q)
{
 
    // Not possible
    if (y % x != 0)
        return -1;
 
    int d = y / x;
 
    // To store the greatest power
    // of p that divides d
    int a = 0;
 
    // While divisible by p
    while (d % p == 0) {
        d /= p;
        a++;
    }
 
    // To store the greatest power
    // of q that divides d
    int b = 0;
 
    // While divisible by q
    while (d % q == 0) {
        d /= q;
        b++;
    }
 
    // If d > 1
    if (d != 1)
        return -1;
 
    // Since, d = p^a * q^b
    return (a + b);
}
 
// Driver code
int main()
{
    int x = 12, y = 2592, p = 2, q = 3;
 
    cout << minOperations(x, y, p, q);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to return the minimum
    // operations required
    static int minOperations(int x, int y, int p, int q)
    {
     
        // Not possible
        if (y % x != 0)
            return -1;
     
        int d = y / x;
     
        // To store the greatest power
        // of p that divides d
        int a = 0;
     
        // While divisible by p
        while (d % p == 0)
        {
            d /= p;
            a++;
        }
     
        // To store the greatest power
        // of q that divides d
        int b = 0;
     
        // While divisible by q
        while (d % q == 0)
        {
            d /= q;
            b++;
        }
     
        // If d > 1
        if (d != 1)
            return -1;
     
        // Since, d = p^a * q^b
        return (a + b);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int x = 12, y = 2592, p = 2, q = 3;
        System.out.println(minOperations(x, y, p, q));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the minimum
# operations required
def minOperations(x, y, p, q):
 
    # Not possible
    if (y % x != 0):
        return -1
 
    d = y // x
 
    # To store the greatest power
    # of p that divides d
    a = 0
 
    # While divisible by p
    while (d % p == 0):
        d //= p
        a+=1
 
    # To store the greatest power
    # of q that divides d
    b = 0
 
    # While divisible by q
    while (d % q == 0):
        d //= q
        b+=1
 
    # If d > 1
    if (d != 1):
        return -1
 
    # Since, d = p^a * q^b
    return (a + b)
 
 
# Driver code
 
x = 12
y = 2592
p = 2
q = 3
 
print(minOperations(x, y, p, q))
 
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the minimum
    // operations required
    static int minOperations(int x, int y, int p, int q)
    {
     
        // Not possible
        if (y % x != 0)
            return -1;
     
        int d = y / x;
     
        // To store the greatest power
        // of p that divides d
        int a = 0;
     
        // While divisible by p
        while (d % p == 0)
        {
            d /= p;
            a++;
        }
     
        // To store the greatest power
        // of q that divides d
        int b = 0;
     
        // While divisible by q
        while (d % q == 0)
        {
            d /= q;
            b++;
        }
     
        // If d > 1
        if (d != 1)
            return -1;
     
        // Since, d = p^a * q^b
        return (a + b);
    }
     
    // Driver code
    public static void Main ()
    {
        int x = 12, y = 2592, p = 2, q = 3;
        Console.Write(minOperations(x, y, p, q));
    }
}
 
// This code is contributed by anuj_67..

<script>
 
// JavaScript implementation of the approach
 
// Function to return the minimum
// operations required
function minOperations(x, y, p, q){
 
    // Not possible
    if (y % x != 0)
        return -1
 
    var d = Math.floor(y / x)
 
    // To store the greatest power
    // of p that divides d
    var a = 0
 
    // While divisible by p
    while (d % p == 0){
        d = Math.floor(d / p)
        a+=1
    }
 
    // To store the greatest power
    // of q that divides d
    var b = 0
 
    // While divisible by q
    while (d % q == 0){
        d = Math.floor(d / q)
        b+=1
    }
 
    // If d > 1
    if (d != 1)
        return -1
 
    // Since, d = p^a * q^b
    return (a + b)
 
}
 
// Driver code
var x = 12
var y = 2592
var p = 2
var q = 3
 
document.write(minOperations(x, y, p, q))
 
// This code is contributed by AnkThon
 
</script>

6

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra