Valor mínimo que divide a un número y es divisible por otro

Dados dos enteros p y q , la tarea es encontrar el mínimo número x posible tal que q % x = 0 y x % p = 0 . Si las condiciones no se cumplen para ningún número, imprima -1 .
Ejemplos: 
 

Entrada: p = 3, q ​​= 99 
Salida: 3 
99 % 3 = 0 
3 % 3 = 0
Entrada: p = 2, q = 7 
Salida: -1 
 

Enfoque: si un número x satisface la condición dada, entonces es obvio que q se dividirá entre p , es decir , q % p = 0 porque x es un múltiplo de p y q es un múltiplo de x . 
Entonces, el valor mínimo posible de x será el MCD de p y q , y cuando q no sea divisible por p , ningún número satisfará la condición dada.
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 valid number
// that satisfies the given conditions
int minValidNumber(int p, int q)
{
    // If possible
    if (q % p == 0)
        return __gcd(p, q);
    else
        return -1;
}
 
// Driver Code
int main()
{
    int p = 2, q = 6;
    cout << minValidNumber(p, q);
    return 0;
}

//Java  implementation of the approach
 
import java.io.*;
 
class GFG {
     
    // Function to calculate gcd
    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);
    }
 
// Function to return the minimum valid number
// that satisfies the given conditions
static int minValidNumber(int p, int q)
{
    // If possible
    if (q % p == 0)
        return __gcd(p, q);
    else
        return -1;
}
 
// Driver Code
    public static void main (String[] args) {
        int p = 2, q = 6;
        System.out.print(minValidNumber(p, q));
 
 
    // THis code is contributed by  Sachin.
    }
}

# Python3 implementation of the approach
from math import gcd
 
# Function to return the minimum
# valid number that satisfies the
# given conditions
def minValidNumber(p, q) :
 
    # If possible
    if (q % p == 0) :
        return gcd(p, q)
    else :
        return -1
 
# Driver Code
if __name__ == "__main__" :
 
    p, q = 2, 6;
    print(minValidNumber(p, q))
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to calculate gcd
    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);
    }
 
// Function to return the minimum valid number
// that satisfies the given conditions
static int minValidNumber(int p, int q)
{
    // If possible
    if (q % p == 0)
        return __gcd(p, q);
    else
        return -1;
}
 
// Driver Code
public static void Main()
{
    int p = 2, q = 6;
    Console.Write(minValidNumber(p, q));
}
}
 
// THis code is contributed
// by Mukul Singh

<?php
// Php implementation of the approach
 
function gcd($a, $b)
{
 
    // Everything divides 0
    if($b == 0)
 
        return $a ;
 
    return gcd($b , $a % $b);
}
 
// Function to return the minimum valid
// number that satisfies the given conditions
function minValidNumber($p, $q)
{
    // If possible
    if ($q % $p == 0)
        return gcd($p, $q);
    else
        return -1;
}
 
// Driver Code
$p = 2;
$q = 6;
echo minValidNumber($p, $q);
 
// This code is contributed by ita_c
?>

<script>
 
    // Javascript implementation of the approach
     
    // Function to calculate gcd
    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 to return the minimum valid number
    // that satisfies the given conditions
    function minValidNumber(p, q)
    {
        // If possible
        if (q % p == 0)
            return __gcd(p, q);
        else
            return -1;
    }  
     
    let p = 2, q = 6;
    document.write(minValidNumber(p, q));
     
</script>

2

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)